FORCE-T0609E: Minimum Spanning Tree for Each Edge

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

typedef long long lli;
typedef pair<int, int> pii;
typedef tuple<int, int, int, int> tpp;

const int N = 2e5;
const int logN = log2(N);

vector<tpp> edges;
vector<pii> adj[N + 1];
lli ans[N + 1];
int ds[N + 1], sz[N + 1], rnk[N + 1], par[N + 1][logN + 1], mxe[N + 1][logN + 1];
bool isInMST[N + 1];

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

void DFS(int u, int p, int depth, int pw){
    rnk[u] = depth;
    par[u][0] = p;
    mxe[u][0] = pw;
    for(pii nxt : adj[u]){
        int v = nxt.first;
        int w = nxt.second;
        if(v == p){
            continue;
        }
        DFS(v, u, depth + 1, w);
    }
}

int LCAFindMax(int u, int v){
    int mx = 0;
    if(rnk[u] < rnk[v]){
        swap(u, v);
    }
    for(int e = logN; e >= 0; --e){
        if(rnk[par[u][e]] >= rnk[v]){
            mx = max(mx, mxe[u][e]);
            u = par[u][e];
        }
    }
    if(u == v){
        return mx;
    }
    for(int e = logN; e >= 0; --e){
        if(par[u][e] != par[v][e]){
            mx = max(mx, max(mxe[u][e], mxe[v][e]));
            u = par[u][e];
            v = par[v][e];
        }
    }
    mx = max(mx, max(mxe[u][0], mxe[v][0]));
    return mx;
}

int main(){

    int nVertex, nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edges.emplace_back(w, u, v, i);
    }
    sort(edges.begin(), edges.end());
    for(int i = 1; i <= nVertex; ++i){
        ds[i] = i;
        sz[i] = 1;
    }
    lli MSTSum = 0;
    for(tpp t : edges){
        int w = get<0>(t);
        int u = get<1>(t);
        int v = get<2>(t);
        int i = get<3>(t);
        int ru = dsFind(u);
        int rv = dsFind(v);
        if(ru != rv){
            MSTSum += w;
            isInMST[i] = true;
            if(sz[ru] > sz[rv]){
                swap(ru, rv);
            }
            ds[ru] = rv;
            sz[rv] += sz[ru];
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }
    }
    DFS(1, 0, 1, 0);
    for(int e = 1; e <= logN; ++e){
        for(int u = 1; u <= nVertex; ++u){
            par[u][e] = par[par[u][e - 1]][e - 1];
            mxe[u][e] = max(mxe[u][e - 1], mxe[par[u][e - 1]][e - 1]);
        }
    }

    for(tpp t : edges){
        int w = get<0>(t);
        int u = get<1>(t);
        int v = get<2>(t);
        int i = get<3>(t);
        if(isInMST[i]){
            ans[i] = MSTSum;
            continue;
        }
        ans[i] = MSTSum - LCAFindMax(u, v) + w;
    }
    for(int i = 1; i <= nEdge; ++i){
        cout << ans[i] << '\n';
    }

    return 0;
}