记录编号	536033	评测结果	AAAAAAAAAA
题目名称	[TYVJ 1399]走廊泼水节	最终得分	100
用户昵称	leon	是否通过	通过
代码语言	C++	运行时间	0.305 s
提交时间	2019-07-06 17:34:09	内存使用	13.80 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int fa[6001],n,sum[6001];
struct edge{
	int from,to;
	ll v;
}a[6001];
int find(int x) {
    if(fa[x]==x)
    return x;
    return fa[x]=find(fa[x]);
}
bool cmp(edge a1,edge b1){
	return a1.v<b1.v;
}
int main()
{
		freopen("corridor.in","r",stdin);
	    freopen("corridor.out","w",stdout);
	    int t,a1,b1,c1;
cin>>t;
while(t--){
	ll ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		sum[i]=1;
	}
	for(int i=1;i<=n-1;i++){
		cin>>a1>>b1>>c1; 
		a[i].from=a1;
		a[i].to=b1;
		a[i].v=c1;
	} 
	        sort(a+1,a+n,cmp);
	for(int i=1;i<=n-1;i++){
		int fx=find(a[i].from),fy=find(a[i].to);
		if(fx!=fy){
			ans+=(sum[fx]*sum[fy]-1)*(a[i].v+1);
			fa[fx]=fy;
			sum[fy]+=sum[fx];
			} 
	}
	cout<<ans<<endl; 
	}
	return 0;
}

/*
4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
*/