题意：
T个测试案例
n个点
下面为一棵带权树
问：每个点上站一个人，每个人都走到另一个点上，需要的 总路径和最小 输出这样的路径和
思路：（百度借的）
ans = Σ (每条路长 l )*(经过这条路的最大次数 f )
f = 2 * 这条边左边节点数和右边节点数最小值k. (这样左边的每一个点一定能够对应右边的某个点)
这个k可以dfs 求得.
#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
inline int Max(int a,int b){return a>b?a:b;}
inline int Min(int a,int b){return a<b?a:b;}
#define ll long long
#define N 100010
struct Edge{
int from, to, nex, dis;
}edge[N<<1];
int head[N], edgenum;
void addedge(int u, int v, int dis){
Edge E = {u, v, head[u], dis};
edge[ edgenum ] = E;
head[u] = edgenum++;
}
int num[N], dp[N], n;
ll ans;
void dfs(int u, int fa){
num[u] = 1; dp[u] = 0;
for(int i = head[u]; ~i; i = edge[i].nex){
int v = edge[i].to;
if(v == fa)continue;
dfs(v, u);
num[u] += num[v];
ans += (ll) edge[i].dis* Min( num[v], n-num[v]);
}
}
int main(){
int i, T, Cas = 1;scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(head, -1, sizeof(head)); edgenum = 0;
for(i = 1; i < n; i++)
{
int u, v, d;scanf("%d %d %d",&u,&v, &d);
addedge(u, v, d);
addedge(v, u, d);
}
ans = 0;
dfs(1, -1);
printf("Case #%d: %I64d\n", Cas++, ans<<1);
}
return 0;
}