【题解】
很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。
我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。
显然选择它的儿子作为集合点，它的儿子的子树内的奶牛可以少走当前点到儿子节点的距离dis，不在它儿子的子树内的奶牛要多走dis. 那么我们维护每个节点的子树内的奶牛总数（即点权和），就可以快速进行计算了。效率O(N).
1 #include<cstdio> 2 #include<algorithm> 3 #define N 200010 4 #define rg register 5 #define LL long long 6 using namespace std; 7 int n,tot,last[N],v[N]; 8 LL ans,sum,size[N],dis[N]; 9 struct edge{ 10 int to,pre,dis; 11 }e[N]; 12 inline int read(){ 13 int k=0,f=1; char c=getchar(); 14 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 15 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 16 return k*f; 17 } 18 void dfs(int x,int fa){ 19 size[x]=v[x]; 20 for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=fa){ 21 dis[to]=dis[x]+e[i].dis; 22 dfs(to,x); size[x]+=size[to]; 23 } 24 } 25 void solve(int x,int fa,LL now){ 26 ans=min(ans,now); 27 for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=fa){ 28 LL tmp=now-size[to]*e[i].dis+(sum-size[to])*e[i].dis; 29 solve(to,x,tmp); 30 } 31 } 32 int main(){ 33 n=read(); 34 for(rg int i=1;i<=n;i++) v[i]=read(),sum+=v[i]; 35 for(rg int i=1;i<n;i++){ 36 int u=read(),v=read(),w=read(); 37 e[++tot]=(edge){v,last[u],w}; last[u]=tot; 38 e[++tot]=(edge){u,last[v],w}; last[v]=tot; 39 } 40 dfs(1,0); 41 for(rg int i=1;i<=n;i++) ans+=dis[i]*v[i]; 42 solve(1,0,ans); 43 printf("%lld ",ans); 44 return 0; 45 }