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

    //思路：按边权排序（小到大）依次取出队首元素，则此时连接此边两端点集的长度为此边权+1；
	//而需要连接的边的数量为两点集数量之积-1，因为两集联通而无环，连接两集仅一条边，否则产生回路，与n-1条矛盾 
	#include<bits/stdc++.h>
    using namespace std;
    int n;
    int f[6005];
    int s[6005];
    /*struct node{
    	int to;
    	int cs;
    	node(int x,int y):to(x),cs(y){}
    }pcb[6005];*/
    void Init(){
    	for(int i=1;i<=n;i++){
    	s[i]=1;
    	f[i]=i;}
    }
    int fid(int x){
    	if(x!=f[x]){
    	return f[x]=fid(f[x]);}
    	return x;
    }
    void mg(int x,int y){
    	int fx=fid(x),fy=fid(y);
    	if(s[fx]>=s[fy]){
    		f[fy]=fx;
    		s[fx]+=s[fy];//这里不能只加1（当时脑抽把。。 
    	}
    	else{
    		f[fx]=fy;
    		s[fy]+=s[fx];
    	}
    }
    struct edg{
    	int u,v,c;
    	edg(int x,int y,int z):u(x),v(y),c(z){}
    	bool operator < (edg q)const{return c>q.c;}
    };
    priority_queue<edg> e;
    int main(){
    	freopen("corridor.in","r",stdin);
    	freopen("corridor.out","w",stdout);
    	short t;
    	cin>>t;
    	while(t--){
    		memset(f,0,sizeof(f));
    		cin>>n;
    		Init();
    		int p,q,r;
    		for(int i=0;i<n-1;i++){
    			cin>>p>>q>>r;
    	//		pcb[p].push_back(node(q,r));
    	//		pcb[q].push_back(node(p,r));
    			e.push(edg(p,q,r));
    		}
    	int ans=0;
    	while(!e.empty()){
    		edg tp=e.top();
    		e.pop();
    		if(fid(tp.u)!=fid(tp.v)){
    			ans=ans+(s[fid(tp.u)]*s[fid(tp.v)]-1)*(tp.c+1);
    			mg(tp.u,tp.v);
    		}
    	}
    	cout<<ans<<endl;
    }
    	return 0;
    }