zoj3659长春E

gistfile1.cpp

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define NN 201000



struct Edge{int a,b,c;}edge[NN];

int n,tote,a,b,c,x,y,cnt[NN],set[NN],i;
long long tot[NN],tmp1,tmp2;

inline int cmp(Edge x,Edge y){return x.c>y.c;}

int find(int x){return x==set[x]?x:set[x]=find(set[x]);}

int main(){
    while(scanf("%d",&n)!=EOF){
        
        tote=0;
        for(i=1;i<n;i++){
            scanf("%d%d%d",&a,&b,&c);
            ++tote;
            edge[tote].a=a;edge[tote].b=b;edge[tote].c=c;
        }
        sort(edge+1,edge+n,cmp);
        for(i=1;i<=n;i++){set[i]=i;tot[i]=0;cnt[i]=1;}
    
        for(i=1;i<n;i++){
            a=edge[i].a;
            b=edge[i].b;
            c=edge[i].c;
            x=find(a);y=find(b);
            tmp1=(long long)cnt[y]*c+tot[x];//x
            tmp2=(long long)cnt[x]*c+tot[y];//y
            if (tmp1>tmp2) {
                set[y]=x;
                tot[x]=tmp1;
                cnt[x]=cnt[x]+cnt[y];
            }
            else {
                set[x]=y;
                tot[y]=tmp2;
                cnt[y]=cnt[x]+cnt[y];
            }
         }
         
         printf("%lld\n",tot[find(1)]);
     }
     return 0;
}