[Usaco2010 Mar]gather 奶牛大集会 描述
Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住着C_i(0 <= C_i <= 1,000)只奶牛。在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。
输入
第一行：一个整数N
第二到N+1行：第i+1行有一个整数C_i
第N+2行到2*N行，第i+N+1行为3个整数：A_i,B_i和L_i。
输出
一个数字表示答案
样例
输入
5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3
输出
15
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll tot,head[200002],n,son[200002],cow_num,f[200002],dp[200002],ans=LONG_LONG_MAX; 5 struct data { 6 ll to,nxt,val; 7 } e[200002]; 8 void add(int x,int y,int z) { 9 e[++tot].to=y; 10 e[tot].val=z; 11 e[tot].nxt=head[x]; 12 head[x]=tot; 13 } 14 void dfs(int x,int fa) { 15 for(int i=head[x]; i; i=e[i].nxt) { 16 int v=e[i].to; 17 if(v==fa) 18 continue; 19 dfs(v,x); 20 son[x]+=son[v]; 21 f[x]+=son[v]*e[i].val+f[v]; 22 } 23 } 24 void dfs2(int x,int fa) { 25 ans=min(ans,dp[x]); 26 for(int i=head[x]; i; i=e[i].nxt) { 27 int v=e[i].to; 28 if(v==fa) 29 continue; 30 dp[v]=dp[x]-son[v]*e[i].val+(cow_num-son[v])*e[i].val; 31 dfs2(v,x); 32 } 33 } 34 int main() { 35 scanf("%lld",&n); 36 for(int i=1; i<=n; i++) 37 scanf("%lld",&son[i]),cow_num+=son[i]; 38 for(ll i=1,x,y,z; i<n; i++) 39 scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z),add(y,x,z); 40 dfs(1,0); 41 dp[1]=f[1]; 42 dfs2(1,0); 43 printf("%lld",ans); 44 return 0; 45 }