难度： 绿

算法： 并查集，最小生成树

使用 Kruskal 的思想。每次从最小的边开始，如果加入后无环就加入。

考虑最简单的情况：有三个点，两条边，边权为 $a,b$。为了使唯一的最小生成树包含这两条边，完全图上的第三条边的边权至少要为 $\max(a,b)+1$。我们对输入按边权排序然后遍历，每遍历到一条边就统计至少加多少条边权为多少的边，使之变成完全图，然后加入答案。（加边的数量为完全图的边数减去当前有的边数，边权为当前最大的原始边权 $+1$，原始边是指一开始就有的边）

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,fa[100010],sz[100010],mx[100010],p,ans=0;
struct node{
	ll l,r,w;
}e[100010];
bool cmp(node a,node b){
	return a.w<b.w;
}
ll getfa(ll a){
	if(a==fa[a]) return a;
	return fa[a]=getfa(fa[a]);
}
ll s(ll a){
	return a*(a-1)/2;
}
void un(ll a,ll b,ll c){
	if(sz[a]>sz[b]) swap(a,b);
	sz[b]+=sz[a];
	mx[b]=max(max(mx[b],mx[a]),c);
	fa[a]=b;
	if(s(sz[b])-s(sz[a])-s(sz[b]-sz[a])>1){
		ans+=(s(sz[b])-s(sz[a])-s(sz[b]-sz[a])-1)*(1+mx[b]);
	}
	return ;
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<n;i++) scanf("%lld%lld%lld",&e[i].l,&e[i].r,&e[i].w),ans+=e[i].w;
	sort(e+1,e+n,cmp);
	for(int i=1;i<=n;i++){
		fa[i]=i;
		sz[i]=1;
	}
	for(int i=1;i<n;i++){
		e[i].l=getfa(e[i].l),e[i].r=getfa(e[i].r);
		un(e[i].l,e[i].r,e[i].w);
	}
	printf("%lld",ans);
	return 0;
}