题目地址：https://ac.nowcoder.com/acm/contest/1056/A
思路：
n个节点的树有n条边，先把边从小到大排序，依次扫描每一条边。
如果是一条边，那么就不需要加边
如果是二条边，需要加一条边，这条边的权值应该是当前边的权值+1，如果加边的权值相同，最小生成树就不唯一
如果是三条边，需要加二条边，二条边权值加起来是（当前权值+1）× 2
......

#include<bits/stdc++.h>
using namespace std;
const int maxn=6000+10;
struct rec
{
    int x,y,z;
}edge[maxn*5];
int fa[maxn],s1[maxn],n,m,ans=0,t;//fa为并查集
bool operator <(rec f1,rec f2)
{
    return f1.z<f2.z;
}
int get(int x)//搜索所在集合
{
    if(x==fa[x])
    {
        return x;
    }
    return fa[x]=get(fa[x]);
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n-1;i++)
        {
            cin>>edge[i].x>>edge[i].y>>edge[i].z;
        }
        sort(edge+1,edge+n);//按权值从小到大排序
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
            s1[i]=1;
        }
        ans=0;
        for(int i=1;i<=n-1;i++)
        {
            int x=get(edge[i].x);
            int y=get(edge[i].y);
            if(x==y)
            {
                continue;
            }
            fa[x]=y;//合并集合
            ans+=(edge[i].z+1)*(s1[x]*s1[y]-1);
            s1[y]+=s1[x];
        }
        cout<<ans<<endl;
    }
    return 0;
}