做克鲁斯卡尔的时候维护一个并查集即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N= 6010;
int T;
struct Edge {
int x,y,val;
} e[N];
bool operator < (Edge x,Edge y) {
return x.val<y.val;
}
int n,head[N],ecnt,fa[N],s[N],ans;
int find(int x) {
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
int main() {
cin>>T;
while(T--) {
ans=0;
cin>>n;
for(int i=1; i<n; i++) {
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].val);
}
sort(e+1,e+n);
for(int i=0; i<=6000; i++)
fa[i]=i,s[i]=1;
for(int i=1; i<n; i++) {
int u=find(e[i].x),v=find(e[i].y);
if(u!=v) {
fa[u]=v;
ans+=(e[i].val+1)*(s[u]*s[v]-1);
s[v]+=s[u];
}
}
cout<<ans<<endl;
}
return 0;
}