Minimum spanning tree for each edge

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

struct edge {
    int cost, x, y;
};

vector<pair<int,int>> adj[nax]; // adj -> minimum spanning treeul
vector<edge> edges; // E -> graful initial
vector<int> p(nax); // p -> vectorul de tati pentru DSU
vector<int> sz(nax, 0); // sz -> marimile colectiilor
vector<int> logaritm(nax * 2);
vector<pair<int,int>> euler; // lista euler - constituita din perechi (nod, nivel)
vector<int> first(nax); // prima aparitie a nodului in lista euler
vector<vector<int>> rmq(nax * 2, vector<int> (20, 0));
vector<int> depth(nax); // nivelul fiecarui nod
vector<vector<int>> big(nax, vector<int> (20, 0)); // small[node][x] -> edgeul cu greutate maxima daca urcam 2^x noduri din node
vector<vector<int>> up(nax, vector<int> (20, 0)); // up[node][x] -> in ce nod ajungem daca urcam cu 2^x noduri din node

void dfs(int node, int prdNod, int prdCost, int lvl) {

    up[node][0] = prdNod;
    big[node][0] = prdCost; // urcam cu 2^0 = 1 muchii
    for(int i = 1; i < 20; ++i) {
        up[node][i] = up[up[node][i - 1]][i - 1];
        big[node][i] = max(big[node][i - 1], big[up[node][i - 1]][i - 1]);
    }

    first[node] = euler.size();
    euler.push_back({node, lvl});
    depth[node] = lvl;
    for(auto it : adj[node]) {
        if(it.first == prdNod) {
            continue;
        }
        dfs(it.first, node, it.second, lvl + 1);
        euler.push_back({node, lvl});
    }
}
void computeMins() {
    int n = euler.size();
    for(int i = 0; i < n; ++i) {
        rmq[i][0] = i;
    }
    for(int i = 1; (1 << i) <= n; ++i) {
        for(int j = 0; j + (1 << i) - 1 < n; ++j) {
            int k = rmq[j][i - 1];
            int l = rmq[j + (1 << (i - 1))][i - 1];
            if(euler[k].second < euler[l].second) {
                rmq[j][i] = k;
            } else {
                rmq[j][i] = l;
            }
        }
    }
}
int findLCA(int x, int y) {
    x = first[x];
    y = first[y];

    if(x > y) {
        swap(x, y);
    }
    int len = logaritm[y - x + 1];
    int k = rmq[x][len];
    int l = rmq[y - (1 << len) + 1][len];
    if(euler[k].second < euler[l].second) {
        return euler[k].first;
    }
    return euler[l].first;
}

bool cmp(edge a, edge b) {
    return a.cost < b.cost;
}
int find(int x) {
    return (p[x] == x) ? x : p[x] = find(p[x]);
}
void unite(int x, int y) {
    if(sz[x] > sz[y]) {
        swap(x, y);
    }
    p[x] = y;
    sz[y] += sz[x];
}
int findMax(int x, int y) {
    // y deasupra lui x
    int mx = 0;
    for(int i = 19; i >= 0; --i) {
        if(depth[up[x][i]] >= depth[y]) {
            mx = max(mx, big[x][i]);
            x = up[x][i];
        }
    }
    return mx;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    logaritm[1] = 0;
    for(int i = 2; i < 2 * nax; i++) {
        logaritm[i] = logaritm[i / 2] + 1;
    }

    int n, m;
    cin >> n >> m;

    vector<edge> initEdges; // copie dupa edges

    for(int i = 0; i < m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        edges.push_back(edge{c, x, y});
        initEdges.push_back(edge{c, x, y});
    }

    sort(edges.begin(), edges.end(), cmp);
    for(int i = 1; i <= n; ++i) {
        p[i] = i; // initializarea DSU-ului
        sz[i] = 1;
    }

    int basicCost = 0;

    for(int i = 0; i < edges.size(); ++i) {
        int x = find(edges[i].x), y = find(edges[i].y), cost = edges[i].cost;
        if(x == y) {
            continue;
        }
        unite(x, y);
        adj[edges[i].x].push_back({edges[i].y, cost});
        adj[edges[i].y].push_back({edges[i].x, cost});
        basicCost += cost;
    }

    dfs(1, 1, 0, 0);
    computeMins();

    for(int i = 0; i < m; ++i) {

        int x = initEdges[i].x, y = initEdges[i].y;
        int lca = findLCA(x, y);
        int deletedEdge = max(findMax(x, lca), findMax(y, lca));
        cout << basicCost - deletedEdge + initEdges[i].cost << '\n';

    }
    return 0;
}