莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. p[i]用于合并集合，cnt[i]用于维护节点数量
2. 每两个完全图合并时，新加的边必须大于原有的边，新加的边的数量是双方节点数量相乘-1

可参考： Kruskal算法求最小生成树

#include<bits/stdc++.h>

using namespace std;

const int N = 6010;

int n;
struct Edge
{
    int a,b,w;
    bool operator< (const Edge &t) const
    {
        return w<t.w;
    }
}e[N];
int p[N],cnt[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;

        for(int i=0;i<n-1;i++)
        {
            int a,b,w;
            cin>>a>>b>>w;
            e[i]={a,b,w};
        }

        sort(e,e+n-1);

        for(int i=1;i<=n;i++) p[i]=i,cnt[i]=1;

        int res=0;
        for(int i=0;i<n-1;i++)
        {
            int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
            if(a!=b)
            {
                //新加的边
                res+=(cnt[a]*cnt[b]-1)*(w+1);

                //合并集合
                p[a]=b;

                //维护节点数量
                cnt[b]+=cnt[a];
            }
        }

        cout<<res<<endl;
    }

    return 0;
}