这道题感觉思路非常巧妙， 我是看了别人的博客才想明白的。

这里用到了并查集， 以根节点为中心城市， 然后把边从大到小排序， 每次的当前的边即为容量，

因为是目前的最小值， 然后去算总的容量， 每次选容量大的点作为新的根节点， 也就是新的

中心城市。细节见代码。

#include
    
     #include
     
      #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;}