简要题意：
给定一棵树，求 边权的最小的完全图，使得该完全图的最小生成树为给定的树。
首先，我们回忆一下：求 最小生成树 不外乎两个算法：
- ( exttt{prim})
- ( exttt{kruskal})
它们都是基于贪心的一种算法（只不过选边顺序略区别）。
按照它们的思想来说，每次选一个边权最小的端点属于不同连通块的连接，用并查集维护连通块 即可完成。（( exttt{kruskal}) 算法）
那么，已知了最小生成树：
因为每两个顶点都有边（完全图 的定义），所以应当尽量让 新加的边与已知边接近但不低于（也不等于）当前边。
比方说样例：
那么，如果 (1 ightarrow 3) 这条边 (leq 7)，那么，(2 ightarrow 3) 就可以被它替换，所以，(1 ightarrow 3) 这条边只能是 (geq 7+1)，( herefore) 答案为 (7+4+8 = 19).
所以，对于 (x) 和 (y) 的这条边维护它们当前被连边的个数。（初始为 (1)）然后排序统计，维护并查集完事！
时间复杂度：(O(n+m)).（并查集的常数 (alpha leq 4) 仍然被我忽略）
实际得分：(100pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
typedef long long ll;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
struct node {
int u,v,w;
}; node G[N];
int f[N],n;
ll ans=0,d[N];
inline bool cmp(node x,node y) {
return x.w<y.w;
}
inline int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
int main(){
n=read();
for(int i=1;i<=n;i++) {
f[i]=i; d[i]=1;
if(i!=n) G[i].u=read(),G[i].v=read(),G[i].w=read();
} sort(G+1,G+n,cmp);
for(int i=1;i<n;i++) {
int x=find(G[i].u),y=find(G[i].v);
ans+=G[i].w+(G[i].w+1)*(d[x]*d[y]-1);
d[y]+=d[x]; f[x]=y;
}
// for(int i=1;i<=n;i++) printf("%d ",d[i]); putchar('
');
// for(int i=1;i<=n;i++) printf("%d ",f[i]); putchar('
');
printf("%lld
",ans);
return 0;
}