题意：给你n个点和n-1条边，每个边有边权，每个点是一个城市，每个边是一条路，每个城市只有一个人，每个城市的人都要和另外一个城市的人交换家来住，每一个人都要交换，不会有多个人要和同一个人 交换，问交换的时候，两个城市的人都要走相同的距离，当所有的人家都交换完毕的时候，总路程的最大值。
想法：开始看到这道题，最先想到的是暴力求树的直径，但是时间复杂度是O(n^2)超时，n<=100000，显然是不行的。后来就想不出来了，后来看了学长的资料，发现我们要求得就是每一条边被使用了几次，然后直接就可以算出综合了，后来又在网上查了一下，这就和树的重心由关系了。然后就看了一下，今天太晚了，那题就明天再写。
a---------b我提取一条边，我可以算出b的右边有多少个点，a的左边有多少个点，那么必然e(a,b)被用的次数时MIN(zuo_a,you_a)。这里还有一个要注意的点，就是说，我以一个任意点作为原点进行搜索，所以我不知道是从a往b搜还是反过来，所以要选择MIN_a,MIN_b中小的那一个。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100000+5;
int n,befno,skt[N];
__int64 num[N];
struct node
{int u,v,next,w;
}e[N*2];
int head[N],cnt,vis[N];
void Init()
{memset(head,-1,sizeof(head));cnt=0;
}
void add(int a,int b,int c)
{e[cnt].u=a;e[cnt].v=b;e[cnt].w=c;e[cnt].next=head[a];head[a]=cnt++;
}
void Input()
{scanf("%d",&n);for(int i=1;i<n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c); }
}
int MIN(int x,int y)
{if(x<y) return x;return y;
}
int dfs(int u,int fa)
{int aftno=0;for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(fa==v) continue;aftno+=dfs(v,u);}skt[u]=aftno;return aftno+1;
}
void treatment(int ca)
{__int64 sum=0;memset(skt,0,sizeof(skt));int k=dfs(1,-1);for(int i=0;i<cnt;i+=2){int v=e[i].v;int u=e[i].u;if(skt[u]<skt[v]){swap(u,v);}sum+=2*e[i].w*MIN(skt[v]+1,n-skt[v]-1);}printf("Case #%d: %I64d\n",ca,sum);
}
int main()
{int t,ca=1;scanf("%d",&t);while(t--){Init();Input();treatment(ca++);}return 0;
}
//DFS 方向不确定
//一条边最多用几次
//DFS 子孙个数