LOJ 10067 构造完全图

题目链接

因为要求完全图的最小生成树是给定的\(T\)，那么与树边等效的边边权都要大于树边。
考虑在求最小生成树的过程中，合并两个点集，除了树边的两个端点，两两直接都要连一条权值为\(w+1\)的边。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, fa[N], siz[N];
struct E {
	int u, v, w;
	bool operator < (const E& q) const {
		return w < q.w;
	}
} e[N];

int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

int main() {
    scanf("%d", &n);
	for (int i = 1; i < n; i++) scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
	for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
	sort(e + 1, e + n);
	long long res = 0;
	for (int i = 1; i < n; i++) {
		int u = e[i].u, v = e[i].v, w = e[i].w;
		int uf = find(u), vf = find(v);
		res = res + 1ll * siz[uf] * siz[vf] * (w + 1);
		res -= 1;
		if (siz[uf] > siz[vf]) swap(uf, vf);
		fa[uf] = vf;
		siz[vf] += siz[uf];
	}
	printf("%lld\n", res);
	return 0;
}