这道题感觉思路非常巧妙， 我是看了别人的博客才想明白的。
这里用到了并查集， 以根节点为中心城市， 然后把边从大到小排序， 每次的当前的边即为容量，
因为是目前的最小值， 然后去算总的容量， 每次选容量大的点作为新的根节点， 也就是新的
中心城市。细节见代码。
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 212345;
struct node
{ll u, v, w;bool operator < (const node& rhs) const{return w > rhs.w;}
}Edge[MAXN];
ll sum[MAXN], cnt[MAXN];
int f[MAXN], n;int find(int x)
{if(f[x] != x)f[x] = find(f[x]);return f[x];
}int main()
{while(~scanf("%d", &n)){REP(i, 1, n + 1) sum[i] = 0, cnt[i] = 1, f[i] = i;REP(i, 0, n - 1) scanf("%lld%lld%lld", &Edge[i].u, &Edge[i].v, &Edge[i].w);sort(Edge, Edge + n - 1);ll ans = 0;REP(i, 0, n - 1){int u = find(Edge[i].u), v = find(Edge[i].v), w = Edge[i].w;ll sumu = sum[u] + cnt[v] * w, sumv = sum[v] + cnt[u] * w;if(sumu < sumv) f[u] = v, ans = sumv, cnt[v] += cnt[u], sum[v] = sumv;else f[v] = u, ans = sumu, cnt[u] += cnt[v], sum[u] = sumu;} printf("%lld\n", ans);}return 0;
}