记录编号	581272	评测结果	AAAAAAAAAA
题目名称	[TYVJ 1399]走廊泼水节	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2023-07-31 21:44:17	内存使用	2.37 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int t,n;
struct made{
	int x,y,z;
}d[N];
int fa[N],s[N],ans;
int find(int x){
	if(x == fa[x])return x;
	return fa[x] = find(fa[x]);
}
bool cmp(made x,made y){
	return x.z < y.z;
}
int main(){
	freopen("corridor.in","r",stdin);
	freopen("corridor.out","w",stdout);
    scanf("%d",&t);
    while(t--){
    	ans = 0;
    	memset(d,0,sizeof(d));
    	memset(fa,0,sizeof(fa));
    	memset(s,0,sizeof(s));
    	scanf("%d",&n);
    	for(int i = 1;i < n;i++)
    		scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z);
		for(int i = 1;i <= n;i++)fa[i] = i,s[i] = 1;
		//s[x]表示以x为根的并查集有多少个节点 
		/*当边(x,y,z)中,x属于并查集Sx,y属于并查集Sy
		肯定要在Sx与Sy两集合中连除这条边的所有边
		又要保证边(x,y,z)为最小生成树的一边
		所以把其他边的权值定位z+1
		去掉这条边,两集合共需要添加|Sx|*|Sy|-1条边,然后和并查集 
		*/ 
		sort(d+1,d+n,cmp);//从小往大找 
		for(int i = 1;i < n;i++){
			int x = find(d[i].x),y = find(d[i].y);
			if(x == y)continue;
			fa[x] = y;
			ans += (d[i].z + 1) * (s[x] * s[y] - 1);
			s[y] += s[x];//并查集合并 
		}
		printf("%d\n",ans);
	}
	
	return 0;
	
}