走廊泼水节

#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N=6010;
typedef long long ll;
typedef pair<int,int> PII;
#define x first
#define y second

int n;
struct node{
    int a,b;
    double w;
    bool operator<(const node& W)const
    {
        return w<W.w;
    }
}e[N];
int p[N],size[N];

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

void solve()
{
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[i]={a,b,c};
    }
    
    for(int i=1;i<=n;i++) p[i]=i;size[i]=1;//size初始化为1
    
    sort(e,e+n-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+=(size[a]*size[b]-1)*(w+1);//减1是把所加的这条边减去
            size[b]+=size[a];//维护每个连通块中结点的数目
            p[a]=b;
        }
    }
    cout<<res<<endl;
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}