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

stdp · 2025-10-01 21:25:40 · 题解

真的有人能在考场上默写出这题吗？

考虑对于边的位置分类讨论，对于非树边，答案即为原图最小生成树的边权和。

对于树边，会将最小生成树分为两个连通块，答案即为所有连接两个连通块的边的最小值。

考虑这个如何维护，不妨把题目转化一下。注意到断掉的边刚好在连接边的路径上。于是我们可以枚举所有非树边，然后更新路径上的最小值。

这个可以用倍增表维护。

最后增加的答案即为连上的边减去断掉的边，注意特判 -1。

#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;
}