LibreOJ #10067 构造完全图（由最小生成树构造最小完全图）

题目链接：https://loj.ac/problem/10067

完全图：
若一个图的每一对不同顶点恰有一条边相连，则称为完全图。
完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n − 1) / 2条边。由
最小生成树复原最小完全图：
最小生成树T，T中的每一条边都是一条割边
去掉任意一条树T中的边，这个树一定会变成两个联通块，令其为A、B。
要将T扩展为完全图G，那么显然 A中的每个点都需要与B中的所有点相连。
A中新发出的连边的权值一定是大于（若等于则存在多种最小生成树解，不合题意）出发点在树上的相接边的权值的。
再一看数据量，单独枚举肯定不行。由联通块可以联想到并查集，发现可行。
对于一条最小生成树上的边E<A,B>，可以看做E连接了A,B两个联通块。
那么要将A、B两块连接为一个完全图需要加的边数就是 cnt[A] * cnt[B]-1，其中cnt表示联通块中的结点个数。
边的权值一定是大于E的权值的，要使其最小，那么这些边的权值都是 E的权值+1
那么合并A、B两个联通块的花费就是 (边E.权+1)*(cnt[A]*cnt[B]-1)。ans在每次合并联通块时加上花费即可求解。
另外一点，因为要求的是最小的完全图，所以有一个贪心策略：先把树上的边按照权值从小到大排序，然后枚举即可。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long LL;
struct node
{
    int u,v;
    LL w;
} val[N];
int n,f[N],ans[N];
int getf(int x)
{
    if(x!=f[x])
        f[x]=getf(f[x]);
    return f[x];
}
int cmp(node t1,node t2)
{
    return t1.w<t2.w;
}
int main()
{
    scanf("%d",&n);
    LL sum=0;
    for(int i=1; i<n; i++)
    {
        scanf("%d%d%lld",&val[i].u,&val[i].v,&val[i].w);
        sum+=val[i].w;
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        ans[i]=1;
    }
    sort(val+1,val+n,cmp);
    for(int i=1; i<n; i++)
    {
        int t1=getf(val[i].u);
        int t2=getf(val[i].v);
        sum+=(LL)(val[i].w+1)*(ans[t1]*ans[t2]-1);
        f[t1]=t2;
        ans[t2]+=ans[t1];
    }
    printf("%lld\n",sum);
    return 0;
}