2796 最小完全图

/*树就是不存在环的图，而完全图就要求我们把树上的点间关系全部变成环 首先把各边从小到大排序，以保证从小的开始，结果更优 以树上的每条边为基底，进行合并比如用到边i,其端点为a,b将b所在的树合并到a所在的树上,也就是要求两棵小树中所有的点构成一个小的完全图 那么从b树上所有点都向a图上所有点连一条长为v[i]+1的线即可，这样的线一共有siz[a]*siz[b]-1条 上式中"-1"代表的那条边就是边i，其边权为v[i] 就这样跑完最小生成树的所有边，同时将边权累加即可 最后提醒 所有的边权<2^31,别忘了用long long */#include<iostream>#include<cstdio>#include<algorithm>using namespace std;long long siz[20010],n,ans,father[20010];struct node{    long long from,to,v;}e[20010];long long find(long long a){    if(father[a]==a)return father[a];    else return father[a]=find(father[a]);}long long cmp(node a,node b){    return a.v<b.v;}int main(){    scanf("%d",&n);    for(long long i=1;i<n;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].v);    for(long long i=1;i<=n;i++)father[i]=i,siz[i]=1;    sort(e+1,e+n,cmp);    for(long long i=1;i<n;i++){        long long a=e[i].from,b=e[i].to;        long long f1=find(a),f2=find(b);        father[f2]=f1;        ans+=e[i].v;        long long value=http://www.mamicode.com/siz[f1]*siz[f2]-1;        ans+=value*(e[i].v+1);        siz[f1]+=siz[f2];//与19行对应，注意是谁变成了谁的子树     }    cout<<ans;}