刷题记录表

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(ll &a){a=0;int f=1;char c=getchar();if(c==EOF) return a=EOF;
for(;c<'0' || c>'9';c=getchar()){if(c=='-') f=-1;if(c==EOF) return a=EOF;}
for(;c<='9' && c>='0';a=a*10+c-'0',c=getchar());return a*=f;}
ll n;
//struct tree{
//	int next,ver,val;
//} e[200010];
//int head[100010],tot;
//void add(int a,int b,int c){e[++tot].next=head[a],head[a]=tot,e[tot].ver=b,e[tot].val=c;
//e[++tot].next=head[b],head[b]=tot,e[tot].ver=a,e[tot].val=c;}
struct Bb{
	ll s,t,d;
} a[100010];
ll ans;
ll bj[100010],fa[100010];

ll find(ll x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

bool sort1(Bb a,Bb b){return a.d<b.d;}

int main()
{
	read(n);
	for(ll i=1;i<n;i++) read(a[i].s),read(a[i].t),read(a[i].d),ans+=a[i].d;
	for(ll i=1;i<=n;i++) fa[i]=i,bj[i]=1;
	sort(a+1,a+n,sort1);
	for(ll i=1;i<n;i++)
	{
		ll x=find(a[i].s),y=find(a[i].t);
		if(x!=y) ans+=(bj[x]*bj[y]-1)*(a[i].d+1),fa[y]=x,bj[x]+=bj[y];
	}
	printf("%lld",ans);
	return 0;
}