题解 BZOJ 2238 Mst | 树上倍增

给出 n 个点，m 条边的无向带权图，q 次询问，询问在图中删掉一条边后的 \text{MST} 的边权和。询问独立。

n \leq 5 \times 10^4, m \leq 10^5。

SJX 大爷教我的（

记原图的 \text{MST} = (E_{\text{MST}}, V_{\text{MST}})。

对于 e(u, v, w) \not \in E_{\text{MST}}（下文称为非树边），将它删去后显然不会对答案造成任何影响。

对于 e(u, v, w) \in E_{\text{MST}}（下文称为树边），将它删去后，为了使得点 u, v 仍然连通，我们必须要找一条非树边代替之，且这条非树边 e'(u', v', w') 所连接的顶点 (u', v')，在 \text{MST} 上的路径必定覆盖了 (u, v)。

自然的，我们想到枚举每一条非树边，并将其所连接的两个节点在 \text{MST} 上的路径中的所有树边更新。

更具体的，记 f_e（其中 e 为一条树边）为能代替 e 的非树边的最小权值。一开始 f_e = +\infty。对于枚举到的非树边 e'(u', v', w')，更新所有 e \in E'（其中 E' 代表 (u', v') 在 \text{MST} 上的路径）的 f_e \leftarrow \min(f_e, w')。

问题转化为如何维护这个过程。

一个经典的解法是利用树链剖分与线段树，网络上大多数的题解也是如此。不过这样做的复杂度是 O(n \log n^2) 的，且代码长度较长。

我们采用一种码量更少，复杂度更为优秀的 O(n \log n) 算法，树上倍增来解决。

记录倍增数组 \text{fa}(u, k) 表示 u 的 2^k 级祖先。

令标记 \text{tag}(u, k) 表示从 u 到其 2^k 级祖先的链上被更新的延时标记。易知整个算法就是要回答 \text{tag}(u, 0)。

考虑倍增求 LCA 的过程，同样的，我们不断从 u', v' 向上跳，直到相遇，同时打上标记即可。

最后将标记下传，即

\text{tag}(u, i - 1) \leftarrow \min(\text{tag}(u, i - 1), \text{tag(u, i)})\\ \text{tag}(\text{fa}(u, i - 1), i - 1) \leftarrow \min(\text{tag}(\text{fa}(u, i - 1), i - 1), \text{tag}(u, i))

感性理解起来就是将 u 到 \text{fa}(u, i) 的链分成下传给两半。

至此，对于删除树边 e(u, v, w)，其答案为:

\text{MST}_w - w + \text{tag}(u, 0)

（这里我们假设 u 在 \text{MST} 上的深度更深一点）。

代码实现上有一些区别。

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

const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;
const int MAX_LOG = 17;
const int INF = 1e9;

int n, m, mstval, q;

void chkmin(int& a, int b) { if (a > b) a = b; }

namespace G {
    int head[MAXN], e_cnt;
    int dwn[MAXN << 1];
    struct Edge { int nxt, to, id; } e[MAXN << 1];
    void add(int u, int v, int id) { e[++e_cnt].nxt = head[u], e[e_cnt].to = v, e[e_cnt].id = id, head[u] = e_cnt; }
    struct Vertix { int dep, fa, ff[MAX_LOG + 3], tag[MAX_LOG + 3]; } vtx[MAXN];
    void dfs(int u) {
        vtx[u].dep = vtx[vtx[u].fa].dep + 1, vtx[u].ff[0] = vtx[u].fa, vtx[u].tag[0] = INF;
        for (int i = 1; i <= MAX_LOG; ++i) vtx[u].ff[i] = vtx[vtx[u].ff[i - 1]].ff[i - 1], vtx[u].tag[i] = INF;
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].fa) continue;
            vtx[v].fa = u, dwn[e[_].id] = v, dfs(v);
        }
    }
    void update(int u, int v, int w) {
        if (vtx[u].dep < vtx[v].dep) swap(u, v);
        for (int i = MAX_LOG; ~i; --i) if (vtx[u].dep - (1 << i) >= vtx[v].dep) {
            chkmin(vtx[u].tag[i], w), u = vtx[u].ff[i];
        }
        if (u == v) return ;
        for (int i = MAX_LOG; ~i; --i) if (vtx[u].ff[i] != vtx[v].ff[i]) {
            chkmin(vtx[u].tag[i], w), chkmin(vtx[v].tag[i], w);
            u = vtx[u].ff[i], v = vtx[v].ff[i];
        }
        chkmin(vtx[u].tag[0], w), chkmin(vtx[v].tag[0], w);
    }
}

namespace Kruskal {
    struct DSU {
        int fa[MAXN];
        void init() { iota(fa + 1, fa + n + 1, 1); }
        int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }
        void merge(int x, int y) { if (gf(x) != gf(y)) fa[gf(y)]= gf(x); }
    } dsu;
    struct Edge { int u, v, w, id; bool operator <(const Edge& _) const { return w < _.w; } } e[MAXN], cpy[MAXN];
    int kruskal() {
        sort(e + 1, e + m + 1);
        dsu.init();
        int cnt = 0;
        for (int i = 1; i <= m && cnt < n - 1; ++i) {
            if (dsu.gf(e[i].u) != dsu.gf(e[i].v)) {
                mstval += e[i].w;
                dsu.merge(e[i].u, e[i].v), cnt++;
                G::add(e[i].u, e[i].v, e[i].id), G::add(e[i].v, e[i].u, e[i].id);
            }
        }
        if (cnt < n - 1) { return -1; }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w); Kruskal::e[i] = {u, v, w, i}, Kruskal::cpy[i] = Kruskal::e[i];
    }
    scanf("%d", &q);
    if (Kruskal::kruskal() == -1) { for (int i = 1; i <= q; ++i) puts("Not connected"); return 0; }
    G::dfs(1);
    for (int i = 1; i <= m; ++i) {
        if (!G::dwn[Kruskal::e[i].id]) G::update(Kruskal::e[i].u, Kruskal::e[i].v, Kruskal::e[i].w);
    }
    for (int i = MAX_LOG; i; --i) {
        for (int j = 1; j <= n; ++j) {
            chkmin(G::vtx[j].tag[i - 1], G::vtx[j].tag[i]);
            chkmin(G::vtx[G::vtx[j].ff[i - 1]].tag[i - 1], G::vtx[j].tag[i]);
        }
    }
    for (int _ = 1; _ <= q; ++_) {
        int t; scanf("%d", &t);
        if (!G::dwn[t]) printf("%d\n", mstval);
        else {
            int ans = G::vtx[G::dwn[t]].tag[0];
            if (ans == INF) puts("Not connected");
            else printf("%d\n", mstval - Kruskal::cpy[t].w + ans);
        }
    }
    return 0;
}

感觉这方法还可以拓展？