思路：其实就是让每一条路有尽量多的人走。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Maxn 100010 #define Maxm 100010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 0x7fffffff #define Mod 1000000007 using namespace std; struct Edge{ int u,v,next; LL val; }edge[Maxm*2]; LL dp[Maxn],sum[Maxn],n; int e,vi[Maxn],head[Maxn]; void init() { memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); memset(head,-1,sizeof(head)); memset(vi,0,sizeof(vi)); e=0; } void add(int u,int v,LL val) { edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++; edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++; } void dfs(int u) { int i,v; sum[u]=1; dp[u]=0; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v; if(vi[v]) continue; dfs(v); LL num=min(sum[v],n-sum[v]); dp[u]+=dp[v]+num*edge[i].val*2; sum[u]+=sum[v]; } // cout<<u<<" "<<dp[u]<<endl; } int main() { int t,i,j,u,v,Case=0; LL val; scanf("%d",&t); while(t--){ init(); scanf("%I64d",&n); for(i=1;i<n;i++){ scanf("%d%d%I64d",&u,&v,&val); add(u,v,val); } dfs(1); printf("Case #%d: %I64d ",++Case,dp[1]); } return 0; }