MST for Each Edge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MAXN = 2e5;
const int MAXL = 20;  // approximately maximum log
 
// for euler-tour
array<int, MAXN> enter_time, exit_time, depth;
 
// up[i][j] stores the 2^jth ancestor of vertex i (for binary lifting)
array<array<int, MAXL>, MAXN> up;
 
/*
 * max_up[i][j] stores the maximum weight of all the edges
 * from i to its 2^jth ancestor
 */
array<array<int, MAXL>, MAXN> max_up;
 
map<pair<int, int>, int> weights;  // weight of edge {i, j}
vector<int> graph[MAXN];           // adjacency list for the original MST
int timer = 1;
int n, m;
 
struct Edge {
	// bidirectional edge from u to v
	int index, u, v, weight;
};
 
// here we build the MST using kruskals' algorithm
// it returns the sum of the weights that took to build the MST
ll kruskal(vector<Edge> &edges) {
 
	// sort by non-decreasing weight
	sort(edges.begin(), edges.end(),
	     [&](Edge a, Edge b) { return a.weight < b.weight; });
 
	// implementation of basic Disjoint Set Union
	vector<int> parent(n), sz(n, 1);
	iota(parent.begin(), parent.end(), 0);
 
	function<int(int)> get = [&](int x) {
		if (parent[x] != x) { parent[x] = get(parent[x]); }
		return parent[x];
	};
 
	// returns true if the vertices are not already united
	function<bool(int, int)> unite = [&](int x, int y) {
		int parent_x = get(x), parent_y = get(y);
		if (sz[parent_x] < sz[parent_y]) { swap(parent_x, parent_y); }
		if (parent_x != parent_y) {
			parent[parent_y] = parent_x;
			sz[parent_x] += sz[parent_y];
			return true;
		}
		return false;
	};
 
	ll total_cost = 0;
	for (Edge e : edges) {
		if (unite(e.u, e.v)) {
			total_cost += e.weight;
			graph[e.u].push_back(e.v);
			graph[e.v].push_back(e.u);
		}
	}
 
	return total_cost;
}
 
void euler_tour(int vertex, int parent) {
	enter_time[vertex] = timer++;
	depth[vertex] = depth[parent] + 1;
 
	// initialize binary lifting arrays
	up[vertex][0] = parent;
	max_up[vertex][0] = weights[{parent, vertex}];
 
	for (int child : graph[vertex]) {
		if (child != parent) { euler_tour(child, vertex); }
	}
 
	exit_time[vertex] = timer - 1;
}
 
bool is_ancestor(int x, int y) {
	return enter_time[x] <= enter_time[y] && exit_time[y] <= exit_time[x];
}
 
int lca(int x, int y) {
	if (is_ancestor(x, y)) { return x; }
	for (int i = MAXL - 1; i >= 0; i--) {
		if (!is_ancestor(up[x][i], y)) { x = up[x][i]; }
	}
	return up[x][0];
}
 
// get maximum weight of all the edges from x to its kth ancestor
int get_max_up(int x, int k) {
	int res = 0;
	for (int i = 0; i < MAXL; i++) {
		if (k & (1 << i)) {
			res = max(res, max_up[x][i]);
			x = up[x][i];
		}
	}
	return res;
}
 
int main() {
	cin >> n >> m;
 
	vector<Edge> edges(m);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		edges[i] = {i, --u, --v, w};
		weights[{u, v}] = w;
		weights[{v, u}] = w;
	}
	ll total_cost = kruskal(edges);
 
	euler_tour(0, 0);
 
	// fill binary-lifting arrays
	for (int k = 1; k < MAXL; k++) {
		for (int i = 0; i < n; i++) {
			up[i][k] = up[up[i][k - 1]][k - 1];
			// take max of weights from left and right
			max_up[i][k] = max(max_up[i][k - 1], max_up[up[i][k - 1]][k - 1]);
		}
	}
 
	vector<ll> ans(m);
	for (Edge e : edges) {
		int least_common_ancestor = lca(e.u, e.v);
		int max_u = get_max_up(e.u, depth[e.u] - depth[least_common_ancestor]);
		int max_v = get_max_up(e.v, depth[e.v] - depth[least_common_ancestor]);
		ans[e.index] = total_cost - max(max_u, max_v) + e.weight;
	}
 
	for (int i = 0; i < m; i++) { cout << ans[i] << "\n"; }
}