题解 | #走廊泼水节#

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 201000;
 
int n,t; 
int p[N],cnt[N];
 
 
struct Node
{
    int x,y,z;
}st[N]; 
 
bool cmp(Node a,Node b)
{
    return a.z<b.z;
}
 
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
 
void Kruskal()
{
    int res=0;
 
    for(int i=0;i<n-1;i++)
    {
        int a=st[i].x,b=st[i].y,c=st[i].z;
 
        a=find(a),b=find(b);
 
        if(a!=b)
        {
            res+=(cnt[a]*cnt[b]-1)*(c+1); 
        	cnt[b]+=cnt[a];
            p[a]=b;
        }
    }
    cout<<res<<'\n';
}
 
int main()
{
    cin>>t;
    while(t--)
    {
    	cin>>n;
	    for(int i=1;i<=n;i++) p[i]=i,cnt[i]=1;
	 
	    for(int i=0;i<n-1;i++)
	    {
	        cin>>st[i].x>>st[i].y>>st[i].z;
	    }
	 
	    sort(st,st+n-1,cmp);
	 
	    Kruskal();
	}
 
    return 0;
}