题解

我们先按Kruskal在已经给出的最小生成树模拟，每次按边权从小到大对联接的两个块操作

一步一步合并节点，每次两个完全图集合互相合并成一个完全图集合时，ans要加上(这条路最小权值+1)(集合一的点数集合二的点数-1)

码量较小，主要考察思维

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int x,y,w;
};
const int maxn=50010;
int fa[maxn],s[maxn];
edge a[maxn];
bool cmp(const edge &a,const edge &b){
    return a.w<b.w;
}
int father(int x){
    if(fa[x]==x) return x;
    fa[x]=father(fa[x]);
    return father(fa[x]);
}
int main(){
    int t;
    int x,y,w,n;
    scanf("%d",&t);
    while(t--){
        int ans=0;
        scanf("%d",&n);
        for (int i=0;i<=n;i++) fa[i]=i,s[i]=1;
        for (int i=1;i<=n-1;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
        sort(a+1,a+n,cmp);
        for(int i=1;i<=n-1;i++)
        {
            int x=father(a[i].x);
            int y=father(a[i].y);
            if(x==y) continue;
            ans+=(a[i].w+1)*(s[x]*s[y]-1); 
            fa[x]=y;
            s[y]+=s[x];
        }
        printf("%lld\n",ans);
    }
    return 0;
}