#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#include<cstdio>
#define MAXN 200005
using namespace std;
int F[MAXN];
int num[MAXN];
ll s[MAXN];
struct Edge{
int a,b,cost;
}e[MAXN];
int cmp(Edge &a,Edge &
b){
return a.cost>
b.cost;
}
int find(
int x){
if(F[x]==-
1)
return x;
return F[x]=
find(F[x]);
}
int main(){
int n;
while(scanf(
"%d",&n)==
1){
for(
int i=
1;i<=n;i++
){
F[i]=-
1;
num[i]=
1;
s[i]=
0;
}
for(
int i=
0;i<n-
1;i++
)
scanf("%d%d%d",&e[i].a,&e[i].b,&
e[i].cost);
sort(e,e+n-
1,cmp);
//手动合并
int t1,t2;
for(
int i=
0;i<n-
1;i++
){
t1=
find(e[i].a);
t2=
find(e[i].b);
if(t1!=
t2){
s[t2]=max((ll)s[t1]+(ll)e[i].cost*num[t2],(ll)s[t2]+(ll)e[i].cost*
num[t1]);
num[t2]+=
num[t1];
F[t1]=
t2;
}
}
printf("%lld\n",s[t2]);
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/9823361.html
相关资源：各显卡算力对照表！
