CH 6201 走廊潑水節

玄學之門

• 題目：
• 分析：
• 代碼：

題目：

傳送門

分析：

類似 k r u s k a l kruskal kruskal算法的過程，對于一條邊，如果它們的兩個點屬于兩個不同的集合，那麼這些集合間都要連邊，為保證最小生成樹還是資料給出的樹，我們就讓它們都連上 v + 1 v+1 v+1，因為我們需要保證原來樹仍是最小生成樹

(詳見yd書 P 339 P339 P339)

代碼：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring> 
#include<cstdlib>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<ctime>
#include<iomanip>
#include<string>
#include<bitset>
#include<deque>
#include<set>
#define LL long long
#define ch cheap
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
struct node{
	LL x,y,w;
}e[12005];
LL f[6005],s[6005];
LL find(LL i)
{
	return f[i]==i?i:f[i]=find(f[i]);
}
bool cmp(node x,node y) {return x.w<y.w;}
int main()
{
	LL n,t=read(),ans;
	while(t--)
	{
		ans=0;
		n=read();
		for(LL i=1;i<n;i++)
		{
			e[i].x=read();e[i].y=read();e[i].w=read();
		}
		sort(e+1,e+n,cmp);
		for(LL i=1;i<=n;i++) f[i]=i,s[i]=1;
		for(LL i=1;i<n;i++)
		{
			LL a,b;
			a=find(e[i].x);b=find(e[i].y);
			if(a==b) continue;
			f[a]=b;
			ans+=(e[i].w+1)*(s[a]*s[b]-1);
			s[b]+=s[a];
		}
		printf("%lld\n",ans);
	}
	return 0;
}