考虑一条边所做的贡献，为这条边两端的树节点的数目之差的绝对值，因此我们可以搜索，随便钦定一个点为根，然后记录一下每个点子树的大小，那么对于每条边所做的贡献，就是w[i]*abs((n-siz[v[i]])-siz[v[i]])，其中i为边的编号，abs为取绝对值，siz[x]表示x的子树大小，n表示总结点数。
这道题目是树上问题中比较有代表性的一道，其本身并不难，但是可以发现，树上搜索是有效解决树上问题的途径。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #define N 5000005 6 #define int long long 7 using namespace std; 8 int read() 9 { 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} 13 return x*f; 14 } 15 int n,siz[N],v[N],w[N],nxt[N],head[N],cnt,ans; 16 void add(int a,int b,int c) 17 { 18 v[++cnt]=b; 19 w[cnt]=c; 20 nxt[cnt]=head[a]; 21 head[a]=cnt; 22 } 23 void dfs(int x,int fa) 24 { 25 siz[x]=1; 26 for(int i=head[x];i;i=nxt[i]) 27 { 28 if(v[i]==fa)continue; 29 dfs(v[i],x); 30 siz[x]+=siz[v[i]]; 31 ans+=w[i]*abs(siz[v[i]]-(n-siz[v[i]])); 32 } 33 } 34 signed main() 35 { 36 n=read(); 37 for(int x,y,z,i=1;i<n;i++) 38 { 39 x=read();y=read();z=read(); 40 add(x,y,z);add(y,x,z); 41 } 42 dfs(1,0); 43 cout<<ans<<endl; 44 return 0; 45 }