题目测试的时候感觉题就很恶心，10道都不会，，不过在正式比赛的时候还是有队伍犀利的做出了6道，真的很厉害
这个是最水的一题了，但是对我还是很难，看着题解，划拉半天才看明白。
代码优化后JOJ跑了0.57s。（上午刚看明白，下午比赛就出了）
师兄给的题解：
树状DP
因为树是连通的且为无向边，所以可以假定1为根，从结点1开始向各个子树DFS这次DFS过程中要对每个结点记录几个量node[i]记录以i为根的子树（包括i结点）的T[k] 和sum[i]记录以i为根的子树（包括i结点）中，每个结点到根的路径长度*T[k]的和
所以第1遍DFS得到的sum[1]是以1为the most convenient location的答案，那么开始枚举以不同结点为the most convenient location的情况对于下图
1 / \ 2 3/4
比如转移到2节点，则以2节点为the most convenient location 的答案是
Sum[1] – sum_node[2] * g[1][2] + ( sum_node[1] – sum_node[2]) * g[1][2] = Sum[2]
（g[1][2]表示1到2这条边的权值）
接着对于以4节点为the most convenient location 的答案是
Sum[2] – sum_node[4] * g[2][4] + ( sum_node[1] – sum_node[4]) * g[2][4] = Sum[4]
以此类推，这样子DFS一遍即可
#include <cstdio>#include <string.h>const int maxn=100005;struct Edge{int v,next,w;}edge[2*maxn];int cnt,n,head[maxn];long long node[maxn],sum[maxn],sum_node[maxn];bool vis[maxn];void addedge(int u,int v,int w){edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].v=u;edge[cnt].w=w;edge[cnt].next=head[v];head[v]=cnt++;}void dfs (int u){int v,i,t=head[u],w;vis[u]=true ;sum_node[u]=node[u];for (;~t;t=edge[t].next){v=edge[t].v;if(vis[v])continue;w=edge[t].w;dfs(v);sum_node[u]+=sum_node[v];sum[0]+=w*sum_node[v];}}void dfs2 (int u){int v,t,w;vis[u]=true ;for (t=head[u]; ~t ; t=edge[t].next){v=edge[t].v;if(vis[v])continue;w=edge[t].w;sum[v]=sum[u]+(sum_node[0]-(sum_node[v]<<1))*w;dfs2(v);}}inline void init (){memset (head , -1 ,sizeof(head));memset (vis , 0 , sizeof(vis));sum[0]=0;cnt=0;}long long sovle (){int i;dfs(0);memset (vis , false , sizeof(vis));dfs2(0);long long min_num=sum[0];for (i=0 ; i<n ; ++i)if(min_num>sum[i]) min_num=sum[i];return min_num;}int main (){int i,u,v,w;while (~scanf("%d",&n)){init ();for (i=0 ; i<n ; ++i)scanf("%d",node+i);for (i=1 ; i<n ; ++i){scanf("%d%d%d",&u,&v,&w);u–;v–;addedge (u,v,w);}printf("%lld\n",sovle());}return 0;}
你可能付出一定的代价，但日后你得到的，远比付出的多得多。
