给一颗树，带边权，树根是 \(S\)。每次可以给一条边权 \(+1\) 并花费 \(1\) 的代价，求最小代价使得 \(S\) 到所有叶子距离相等。
明显对于任意一个子树都满足到所有叶子距离相等。
所以就开始树形 dp:\(dp_i\) 是 \(i\) 子树的最小操作次数。\(g_i\) 是这个点到其子树叶节点的距离。
因为边权只增不减，所以 \(g_i=\max(g_j)+w(i,j)\)。然后 dp 就是从子树转移过来的，和边权需要加上的：\(dp_i=\sum (dp_j)+\sum(g_i-g_j)\)。
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > e[500005];
long long f[500005],g[500005];
int n,s;
void dfs(int u,int fa){
if(e[u].size()==1&&u!=s)return ;
long long maxx=0;
for(auto E:e[u]){
int v=E.first,w=E.second;
if(v==fa)continue;
dfs(v,u);
maxx=max(g[v]+w,maxx);
}
g[u]=maxx;
for(auto E:e[u]){
int v=E.first,w=E.second;
if(v==fa)continue;
f[u]+=(maxx-(g[v]+w))+f[v];
}
// cout<<u<<" "<<g[u]<<" "<<f[u]<<endl;
}
int main(){
cin>>n>>s;
for(int i=1;i<n;i++){
int x,y,w;
cin>>x>>y>>w;
e[x].push_back(make_pair(y,w));
e[y].push_back(make_pair(x,w));
}
dfs(s,0);
cout<<f[s];
return 0;
}