分析
将边权从小到大排序,然后每次合并两个连通块中所有的点,答案ans要加上(两个连通块的大小的乘积-1)*(边权+1)。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 6010;
int T,n,fa[N],siz[N];
struct node{
int a,b,w;
bool operator<(const node& p)
{
return w<p.w;
}
}edges[N];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
long long ans=0;
cin>>n;
for(int i=0;i<N;i++) fa[i]=i,siz[i]=1;
for(int i=0;i<n-1;i++)
{
cin>>edges[i].a>>edges[i].b>>edges[i].w;
}
sort(edges,edges+n-1); //将边权排序
for(int i=0;i<n-1;i++)
{
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
// cout<<siz[faa]<<" "<<siz[fbb]<<" "<<w+1<<endl;
ans+=(siz[faa]*siz[fbb]-1)*(w+1);
fa[faa]=fbb;
siz[fbb]+=siz[faa];
}
}
cout<<ans<<endl;
}
return 0;
}