https://atcoder.jp/contests/abc214/tasks/abc214_d
Atcoder ABC241 D题
谁能帮忙看一下啊,每次都死在第二个样例555~
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/(gcd(a,b))*b;}
const int MAXN=1e5+5;
int n,ans;
int f[MAXN],sz[MAXN];
struct edge{
int u,v,w;
}e[MAXN];
bool cmp(edge x,edge y){return x.w<y.w;}
int find_set(int x){
if(x!=f[x])f[x]=find_set(f[x]);
return f[x];
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)f[i]=i,sz[i]=1;
for(int i=1;i<n;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e+1,e+n,cmp);
for(int i=1;i<n;i++){
int fau=find_set(e[i].u);
int fav=find_set(e[i].v);
ans+=e[i].w*sz[fau]*sz[fav];
if(fau!=fav){
f[fau]=fav;
sz[fav]+=fau;
}
}
cout<<ans<<endl;
return 0;
}
//ACplease!!!