两遍DFS。第一遍统计以每个点为根的子树大小，第二遍更新答案。

1 #include
     
       2 #include
      
        3 using namespace std; 4 int v[2000001],w[2000001],first[2000001],next[2000001],en,sz[1000001]; 5 bool vis[1000001]; 6 long long ans; 7 inline int Abs(const int &x){
   return x<0 ? -x : x;} 8 inline void AddEdge(const int &U,const int &V,const int &W) 9 {v[++en]=V;w[en]=W;next[en]=first[U];first[U]=en;}10 int n,a,b,c,res;11 char C;12 inline int Get()13 {14     res=0;C='*';15     while(C<'0'||C>'9')C=getchar();16     while(C>='0'&&C<='9'){res=res*10+(C-'0');C=getchar();}17     return res;18 }19 void dfs(int cur)20 {21     vis[cur]=true;22     sz[cur]=1;23     for(int i=first[cur];i;i=next[i])24       if(!vis[v[i]]){dfs(v[i]);sz[cur]+=sz[v[i]];}25     vis[cur]=false;26 }27 void dfs2(int cur)28 {29     vis[cur]=true;30     for(int i=first[cur];i;i=next[i])31       if(!vis[v[i]])32         {33           ans+=(long long)Abs((sz[v[i]]<<1)-n)*w[i];34           dfs2(v[i]);35         }36     vis[cur]=false;37 }38 int main()39 {40     n=Get();41     for(int i=1;i