题解：P14080 [GESP202509 八级] 最小生成树

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

using i32 = int32_t;
using i64 = int64_t;
using ui32 = uint32_t;
using ui64 = uint64_t;

namespace strdp {
	const int N = 1e5;
	int n, m, cnt, q;
	int fa[N + 5];
	struct node { int u, v, w, idx; } a[N + 5];
	bool flg[N + 5];
	struct node2 { int v, w; };
	bool cmp(node x, node y) { return x.w < y.w; }
	vector<node2> g[100005];
	int fd(int x) { if (fa[x] == x) return x; return fa[x] = fd(fa[x]); }
	void jn(int x, int y) { fa[fd(x)] = fd(y); }
	int kruskal() {
		int res = 0;
		for (int i = 1; i <= m; i++) {
			int u = fd(a[i].u), v = fd(a[i].v);
			if (u != v) {
				flg[i] = 1;
				g[a[i].u].push_back({a[i].v, a[i].w});
				g[a[i].v].push_back({a[i].u, a[i].w});
				fa[u] = v; res += a[i].w;
				if (++cnt == n - 1) return res;
			}
		}
	}
	int f[N + 5][21], dep[N + 5], res[N + 5][21];
	bool vis[N + 5];
	void dfs1(int x, int fa) {
		vis[x] = 1; dep[x] = dep[fa] + 1;
		f[x][0] = fa; res[x][0] = LLONG_MAX;
		for (int i = 1; i <= 20; i++) {
			f[x][i] = f[f[x][i - 1]][i - 1];
			res[x][i] = LLONG_MAX;
		}
		for (auto u : g[x]) {
			if (u.v != fa) dfs1(u.v, x);
		}
	}
	int lca(int x, int y) {
		if (dep[x] < dep[y]) swap(x, y);
		for (int i = 20; i >= 0; i--) {
			if (dep[f[x][i]] >= dep[y]) {
				x = f[x][i];
			}
		}
		if (x == y) return x;
		for (int i = 20; i >= 0; i--) {
			if (f[x][i] != f[y][i]) {
				x = f[x][i];
				y = f[y][i];
			}
		}
		return f[x][0];
	}
	void update(int u, int v, int w) {
		int l = lca(u, v);
		for (int i = u; dep[i] > dep[l]; ) {
			int j = f[i][0];
			res[i][0] = min(res[i][0], w);
			i = j;
		}
		for (int i = v; dep[i] > dep[l]; ) {
			int j = f[i][0];
			res[i][0] = min(res[i][0], w);
			i = j;
		}
	}
	int ans[N + 5];
	void main() {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) fa[i] = i;
		for (int i = 1; i <= m; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			a[i] = {u, v, w, i};
		}
		sort(a + 1, a + m + 1, cmp);
		int s = kruskal();
		dfs1(1, 0);
		for (int i = 1; i <= m; i++) if (!flg[i]) update(a[i].u, a[i].v, a[i].w);
		for (int i = 20; i >= 1; i--) {
			for (int j = 1; j <= n; j++) {
				res[j][i - 1] = min(res[j][i - 1], res[j][i]);
				if (f[j][i - 1] != i) res[f[j][i - 1]][i - 1] = min(res[f[j][i - 1]][i - 1], res[j][i]);
			}
		}
		for (int i = 1; i <= m; i++) {
			if (!flg[i]) ans[a[i].idx] = s;
			else {
				if (dep[a[i].u] < dep[a[i].v]) swap(a[i].u, a[i].v);
				if (res[a[i].u][0] == LLONG_MAX) ans[a[i].idx] = -1;
				else ans[a[i].idx] = s - a[i].w + res[a[i].u][0];
			}
		}
		for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
	}
}

i32 main() {

	int t = 1;
	// cin >> t;

	while (t--) strdp::main();
	return 0;
}