// 可以使用一个记录数量的数组cnt[]来维护每个连通块的节点数量
// 只有连通块的根节点数量是正确的,记录了整个连通块的节点数,维护其他点都是没有必要的
// 初始化:
for(1~n) cnt[i]=1;
// 合并连通块
// 这里将bx连通块的根节点设置为by,所以bx连通块的节点数目应加在by上。
if(bx != by){
fa[bx]=by;
cnt[by]+=cnt[bx];
}
code:
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;
typedef pair<int,int> PII;
const int maxn=6010;
int T,n;
int res;
int fa[maxn];
int cnt[maxn];
struct node{
int x,y,z;
}q[maxn];
bool cmp(node a,node b){
return a.z < b.z;
}
int getx(int x){
if(x != fa[x]) fa[x]=getx(fa[x]);
return fa[x];
}
int main()
{
cin>>T;
while(T--){
res=0;
for(int i=0;i<maxn;i++) { // 初始化并查集和连通块数量数组
cnt[i]=1;
fa[i]=i;
}
cin>>n;
for(int i=0;i<n-1;i++){
int u,v,w;
cin>>u>>v>>w;
q[i]={u,v,w};
}
sort(q,q+n-1,cmp); // 从小到大排序
for(int i=0;i<n-1;i++){
int u,v,w;
u=q[i].x,v=q[i].y,w=q[i].z;
int bx=getx(u);
int by=getx(v);
if(bx != by ){ // 有新的连通块加入时
res+=(cnt[bx] * cnt[by] -1 )*(w+1); //累加新增边权值
fa[bx]=by; // 合并连通块
cnt[by]+=cnt[bx]; // 更新连通块根节点的cnt数组(代表连通块数量增加)
}
}
cout<<res<<endl;
}
system("pause");
return 0;
}