构造完全图

咕咕咕

 

由于我好久都没有独立思考了（抄了好久题解），思维什么的早没有了。

看完题只能想到一种暴力：遍历+LCA

题目给出的是一个最小生成树，我们可以从边入手，把每条边所连的左右两个点分别看做一个集合，

左边集合和右边集合所要连的边数是（cnt[i]*cnt[j]-1），-1是因为要抛去本身这条边

我们要连的边权是多大？比当前的边大，

否则就不满足有且仅有一棵最小生成树T，所以边权就为（当前边的边权+1）

我们可以贪心的去解决，把边从小到大排序，并查集一下就行了，当然还得加上原始边的边权。

另外...ans的开long long

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
inline int read()
{int sum = 0,p = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')p = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){(sum *= 10) += ch - '0';ch = getchar();}return sum * p;
}const int N =  1e5 + 5;
int n,fa[N],cnt[N];
ll ans;
struct edge
{int frm,to,wei;
}e[N];bool cmp(edge a,edge b)
{return a.wei < b.wei;
}int findfa(int x)
{return fa[x] == x ? x : findfa(fa[x]);
} void kruskal()
{for(int i = 1;i <= n;i++){fa[i] = i;cnt[i] = 1;}sort(e+1,e+n,cmp);for(int i = 1;i <= n - 1;i++){int u = findfa(e[i].frm);int v = findfa(e[i].to);if(u == v)continue;fa[v] = u;ans += (ll)(cnt[u] * cnt[v] - 1) * (e[i].wei + 1);cnt[u] += cnt[v];}
}int main()
{n = read();for(int i = 1;i <= n - 1;i++){e[i].frm = read();e[i].to = read();e[i].wei = read();ans += (ll)e[i].wei;}kruskal();printf("%lld",ans);return 0;
}