BOJ)10637 Minimum Spanning Tree

문제: icpc.me/10637

간선들의 셋이 주어진다.

출력해야하는 답은 각 간선마다 자신을 제외한 간선들로 만들 수 있는 MST의 가중치의 합을 출력하는 문제이다.

이건 MST에 포함 안되는 간선에 대한 답은 MST의 가중치가 되겠지만 

아닌 경우가 문제가 된다.

그렇다면 아닌 경우에 대해 생각해보자.

만약에 MST에 포함되지 않는 간선이 u-v 를 연결한다고 생각해보자

그러면 우리는 mst에서 u v를 잇는 경로상의 어떤 간선을 지워도 이 간선을 통하여 MST를 유지 할 수 있다.

즉 이러한 사실을 이용하여 MST를 만들 때 사용되지 않은 간선들을 가중치 순서대로 정렬하여

오프라인으로 미리 mst상에 사용 된 간선들의 답을 정해주는 것이다.

여기서 매번 경로를 확인해준다면 당연히 TLE를 보게 될 것이다.

고로 경로압축을 이용해주어야 한다.

경로압축이 가능한 이유는 1.트리에서의 경로이기 때문이고 2.한번 확인한 경로는 더 이상 확인하지 않아도 된다. 라는 조건이 있기 때문이다.

경로압축 방법은 disjoint-set을 이용하고 u-v상의 경로 일 때

u-lca(u,v) / v-lca(u,v) 상의 모든 경로상의 정점의 parent가 lca(u,v)가 되도록 압축해주면 된다.

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
ll n, m, x, y, z, par[100010], mst, cnt, p[100010][22], d[100010], g[100010];
map<pair<ll, ll>, ll> mp;
vector<pair<ll, pair<ll, ll>>> vt, rmd;
vector<vector<pair<ll,ll>>> gph;
vector<pair<ll, ll>> edge;
ll find(ll h) {
    return h == par[h] ? h : par[h] = find(par[h]);
}
void merge(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    par[x] = y;
}
void dfs(ll here, ll prev) {
    d[here] = d[prev] + 1;
    for (auto next : gph[here]) {
        if (next.first == prev)continue;
        p[next.first][0] = here;
        g[next.first] = next.second;
        dfs(next.first, here);
    }
}
ll getlca(ll x, ll y) {
    if (d[x] > d[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (d[y] - d[x] >= (1 << i))
            y = p[y][i];
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--) {
        if (p[x][i] != p[y][i]) {
            x = p[x][i];
            y = p[y][i];
        }
    }
    return p[x][0];
}
void func(ll x, ll y,ll z) {
    ll w;
    if (d[x] < d[y])w = g[y];
    else w = g[x];
    if (x > y)swap(x, y);
    if (mp[{x, y}] == -1)
        mp[{x, y}] = mst - w + z;
}
int main() {
    scanf("%lld%lld", &n, &m);
    gph.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%lld%lld%lld", &x, &y, &z);
        if (x > y)swap(x, y);
        vt.push_back({ z,{x,y} });
        edge.push_back({ x,y });
    }
    sort(vt.begin(), vt.end());
    for (int i = 1; i <= n; i++)
        par[i] = i;
    for (int i = 0; i < m; i++) {
        x = vt[i].second.first;
        y = vt[i].second.second;
        z = vt[i].first;
        if (cnt == n - 1 || find(x) == find(y)) {
            mp[{x, y}] = -2;
            rmd.push_back(vt[i]);
        }
        else {
            cnt++;
            merge(x, y);
            mst += vt[i].first;
            mp[{x, y}] = -1;
            gph[x].push_back({ y ,z });
            gph[y].push_back({ x ,z });
        }
    }
    if (cnt < n - 1) {
        for (int i = 0; i < m; i++)
            puts("-1");
        return 0;
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        par[i] = i;
    for (int i = 1; i < 21; i++) {
        for (int j = 1; j <= n; j++)
            p[j][i] = p[p[j][i - 1]][i - 1];
    }
    for (auto next : rmd) {
        x = find(next.second.first);
        y = find(next.second.second);
        z = next.first;
        ll lca = getlca(x, y);
        ll pa;
        while (find(x) != find(lca)) {
            pa = p[x][0];
            func(x, pa, z);
            merge(x, lca);
            x = find(pa);
        }
        while (find(y) != find(lca)) {
            pa = p[y][0];
            func(y, pa, z);
            merge(y, lca);
            y = find(pa);
        }
    }
    for (int i = 0; i < m; i++)
        printf("%lld\n", mp[{edge[i].first, edge[i].second}] == -2 ? mst : mp[{edge[i].first, edge[i].second}]);
    return 0;
}