[最小生成树变形] vijos

题目
完全图：

引用一个写的不错的题解
其实此题就是变形的最小生成树

每两个点之间都存在且仅存在一条边
由于题中给出的是一个完全图的最小生成树的树边，对于题中给出每一条边（u，v），显然u和v并不连通。因为原图为一个完全图，那么完全图的部分点构成的图也为完全图。假设u所在完全图G1中，G1中有点n1个，v所在完全图G2中，G2中有点n2个，那么，连接边（u，v），并且使得u，v两个完全图合为一个完全图还需要连n1n2-1条边，边权至少要大于边（u，v）的权值，要让完全图边权总和最小，即让这n1n2-1条边的边权为边（u，v）的边权加1即可。
但我们又想到一个问题，怎么保证这样生成的完全图的最小生成树和原题相同？显然，先连接边权大的边，在连接边权小的边，前面连接的边权较大的边会被后面边权小的边连接时补全图为完全图时的边替代。文字难以理解，这里讲一个简单的例子。
3
2 3 7
1 2 4
没错，就是样例，只是将第一条边和第二条边的位置互换，处理时我们从前往后处理。第一条边权值为7，连接后不需要补边（已经为完全图），第二条边权值为4，需要补边（1,3）才能使原图变为完全图，权值为当前边权值加1，即为5，显然，在最小生成树中，边（2,3）会被边（1,3）替代，即操作不合法。
但是，如果我们保证前面的边的边权小于等于后面的边权，那么，求出的完全图的正确性就有保障了。
根据上面所讲，这题和kruskal是不是很像？一开始将边以边权从小到大排序，记录每个点所在集合中的元素个数为d[i]，对于每一条边（u，v），边权为val，ans+=val+（val+1）（d[root[u]]d[root[v]]-1）其中root[i]表示i所在集合的代表元素。最后输出ans即可。

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int x,y,z;
}edge[20005];
int n,fa[20005];
long long ans,d[20005];
bool cmp(node a,node b)
{
    if (a.z<b.z) return true;
    else return false;
}
int find(int x)
{
    if (fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];

int main()

    scanf("%d",&n);
    for (int i=1; i<n; i++)
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
    sort(edge+1,edge+n,cmp);
    for (int i=1; i<=n; i++)
    {
        fa[i]=i;
        d[i]=1;
    }
    for (int i=1; i<n; i++)
    {
        int rx=find(edge[i].x);
        int ry=find(edge[i].y);
        ans+=edge[i].z+(edge[i].z+1)*(d[rx]*d[ry]-1);
        d[ry]+=d[rx];
        fa[rx]=ry;
    }
    printf("%lld\n",ans);    return 0;
}