东莞网站定制,软件编程工具,wape,wordpress 对象储存题意#xff1a;给定一棵N个节点的无根树#xff0c;每条边都有一个权值V#xff0c;选取其中一个点作为关键点#xff0c;你可以任意增加某条边的权值#xff0c;求使得从关键点出发#xff0c;到任意一个叶子节点的距离都相同所需要增加的权值和。 数据范围#xff1a… 题意给定一棵N个节点的无根树每条边都有一个权值V选取其中一个点作为关键点你可以任意增加某条边的权值求使得从关键点出发到任意一个叶子节点的距离都相同所需要增加的权值和。 数据范围 对于40%的数据N ≤ 1000 对于100%的数据N ≤ 500000V ≤ 1000000 -------------------------------------分割线------------------------------------ 题解一道比较显然的树形DP不难想到我们把其他的链都向最长链看齐。 扫描一遍树自底向上处理出当前节点的出边数量num以及当前节点到叶节点的距离和sum。 算出最远的距离激发器的叶子节点距离maxn[x]然后对于其他叶子节点所需要增加的长度显然即为 maxn[x] * num - sum。 累加答案即可。 #includebits/stdc.h#define ll long long
#define mp make_pair
#define rep(i, a, b) for(int i (a); i (b); i)
#define per(i, a, b) for(int i (a); i (b); i--)using namespace std;typedef pairint, int pii;
typedef double db;
const int N 1e6 50;
int n, a[N], root;
int head[N], cnt 0;
ll maxn[N], f[N];
struct node{ ll to, next, v; } e[N];
inline int read(){int x 0, f 1;char ch getchar();while(ch 0 || ch 9) { if(ch -) f -1; ch getchar();}while(ch 0 ch 9) { x (x3)(x1)(ch^48); ch getchar();}return x*f;
}
void add(int x, int y, int z){e[cnt].to y; e[cnt].v z;e[cnt].next head[x]; head[x] cnt;
}
void init(){n read(); root read();rep(i, 1, n-1) {int xx, yy, zz;xx read(); yy read(); zz read();add(xx, yy, zz);add(yy, xx, zz);}
}
void dfs(int x, int fa){f[x] 0, maxn[x] 0;ll sum 0, num 0;for(int i head[x]; i; i e[i].next){int y e[i].to;if(y fa) continue;dfs(y, x); num ;f[x] f[y];maxn[x] max(maxn[y] e[i].v, maxn[x]);sum (ll)maxn[y] e[i].v; }f[x] (ll)maxn[x] * num - sum;
}
void work(){dfs(root, 0);printf(%lld\n, f[root]);
}
int main(){init();work();return 0;
} View Code 转载于:https://www.cnblogs.com/smilke/p/11576955.html
