「TYVJ1391」走廊泼水节

题意：给定一棵 $N$ 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树，求增加的边的权值总和最小是多少。

把每条边按权值从小到大排序，扫描每条边，执行 $Kruskal$ 算法。

设扫描到的边为 $(x,y,z)$ ，$x$ 所在集合为 $S_x$ ，$y$ 所在集合为 $S_y$ ，那么应该合并 $S_x$ 与 $S_y$ 。但是由于我们要在两个集合之间增加若干条边，由于要使最小生成树不变，且增加的权值最小，所以增加边的权值应该为 $z+1$ 。两个集合之间除了最小生成树那条边，还可以连接 $|S_x|\times|S_y|-1$ 条边，所以把 $(z+1)\times (|S_x|\times|S_y|-1)$ 累加到答案中即可求解。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n;
struct edge
{
	int next;
	int to;
	int num;
}e[24101];
int fa[6010],size[6010];
long long ans;
int getfa(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getfa(fa[x]);
}
int cmp(edge a,edge b)
{
	return a.num<b.num;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(fa,0,sizeof(fa));
		memset(size,0,sizeof(size));
		memset(e,0,sizeof(e));
		ans=0;
		scanf("%d",&n);
		for(int i=1;i<n;i++)
			scanf("%d%d%d",&e[i].next,&e[i].to,&e[i].num);
		sort(e+1,e+n,cmp);
		for(int i=1;i<=n;i++)
		{
			fa[i]=i;
			size[i]=1;
		}
		for(int i=1;i<n;i++)
		{
			int x=getfa(e[i].next);
			int y=getfa(e[i].to);
			if(x==y)
				continue;
			ans+=(long long)(size[x]*size[y]-1)*(e[i].num+1);
			fa[x]=y;
			size[y]+=size[x];
		}
		printf("%lld\n",ans);
	}
	return 0;
}