每日归档： 2019年1月10日

有一棵树，每次将一条边的长度增加1的代价为1，求，使得所有叶节点到根节点距离相同的最小代价。
很显然，对于一棵树来说，贪心地考虑，最终的距离显然是最开始的最远叶节点的距离。
然后，继续贪心地考虑，每一次增加的代价，应当避免那些已经是最远距离的节点。
但是这样做的话复杂度最坏是n^2的。
故而我们考虑树形DP。对于每个节点临时记以这个节点为根的子树完成时态同步需要的代价。然后每一次修改把修改结果记下来即可。

#include<iostream>
#include<cstdio>

inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[500005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int n,s,f[500005];
long long ans=0;
inline void dfs(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs(e[i].v,X);
	}
	int mx=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		mx=Max(mx,f[e[i].v]+e[i].w);
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		ans+=mx-(f[e[i].v]+e[i].w);
	}
	f[X]=mx;
}
void init(){
	scanf("%d%d",&n,&s);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(s,0);
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}