P14080题解

consequence · 2025-09-29 21:15:38 · 题解

P14080 题解

其实不算很灵活的一道题。

这里给出树剖的写法（其实有更简单的方法）。

思路分析

先找出并记录整个图的 MST。

对于非树边，答案就是 MST 的大小。对于树边的答案，一定来自这个树边被某一个非树边替换时。而一个非树边可以替换一个树边，当且仅当删掉树边后，树会变成两个部分，再连上这个非树边仍能保证两个部分的连通。但如果单独考虑每条树边，维护每条树边被删掉之后的两个部分之间的最小距离，显然并不容易。

那不妨从另一个角度看，考虑每条非树边对树边答案的贡献。对于原来的树，如果再加上一条非树边，就会出现一个环，而这条非树边，显然能且仅能替换环上所有的树边，而不改变树的连通。而这个环上所有的树边，就是这条非树边两个端点之间的最短路径。那最后每条树边的答案，就是原来 MST 的大小加上所有那些能对它有贡献的非树边的边权的最小值与它本身边权的差值。每条非树边，都可以尝试对其两个端点之间最短路径的所有边更新。

如果你会树链剖分，这就是一个区间修改并维护最小值的问题，可以用线段树实现。特别地，为方便处理，我们假设每个节点的值代表它们与父亲节点之间的树边的答案（根节点不代表任何边的答案），这样在做区间修改时要注意不修改两个端点最近公共祖先的值。

如果一个树边从头到尾都没被更新，说明它无法被替换，就是删去它无论如何都无法使图连通（割边），特判并输出 -1 即可。

时间复杂度 O(n \log^2 n)。

以下给出代码（有段时间没碰 OI，写得比较丑陋，见谅）

#include <bits/stdc++.h>
#define fr first
#define sc second
#define mp make_pair
#define pii pair

using namespace std;

const int MAXN = 1e5 + 10;
int n, m, cnt;
long long ans;
bool hs[MAXN], it[MAXN], flag[MAXN];
long long d[MAXN], fans[MAXN];
int f[MAXN], son[MAXN], sz[MAXN], id[MAXN], top[MAXN];
vector<pii<long long, pii<int, int>>> v[MAXN];

struct Node {
    int l, r;
    long long dat, add;
}t[4 * MAXN];

void built(int p, int L, int R) {
    t[p].l = L;
    t[p].r = R;
    t[p].add = LLONG_MAX;
    t[p].dat = LLONG_MAX;
    if (L == R) return;
    int mid = (L + R) >> 1;
    built(p * 2, L, mid);
    built(p * 2 + 1, mid + 1, R);
}
void spread(int p) {
    if (t[p].add == LLONG_MAX) return;
    t[p * 2].dat = min(t[p].add, t[p * 2].dat);
    t[p * 2 + 1].dat = min(t[p].add, t[p * 2 + 1].dat);
    t[p * 2].add = min(t[p * 2].add, t[p].add);
    t[p * 2 + 1].add = min(t[p * 2 + 1].add, t[p].add);
    t[p].add = LLONG_MAX;
}
void change(int p, int L, int R, long long k) {
    if (L <= t[p].l && R >= t[p].r) {
        t[p].dat = min(t[p].dat, k);
        t[p].add = min(t[p].add, k);
        return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (L <= mid) change(p * 2, L, R, k);
    if (R > mid) change(p * 2 + 1, L, R, k);
    t[p].dat = min(t[p * 2].dat, t[p * 2 + 1].dat);
}
void schange(int p, int L, int R, long long k) {
    if (L <= t[p].l && R >= t[p].r) {
        t[p].dat = k;
        return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (L <= mid) schange(p * 2, L, R, k);
    if (R > mid) schange(p * 2 + 1, L, R, k);
    t[p].dat = min(t[p * 2].dat, t[p * 2 + 1].dat);
}
long long ask(int p, int L, int R) {
    if (L <= t[p].l && R >= t[p].r) return t[p].dat;
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    long long val = LLONG_MAX;
    if (L <= mid) val = min(val, ask(p * 2, L, R));
    if (R > mid) val = min(val, ask(p * 2 + 1, L, R));
    return val;
}
void fchange(int x, int y, long long k) {
    long long ncnt = ask(1, id[y], id[y]);
    while (top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x, y);
        change(1, id[top[x]], id[x], k);
        x = f[top[x]];
    }
    if (d[x] > d[y]) swap(x, y);
    change(1, id[x], id[y], k);
    schange(1, id[x], id[x], ncnt);//最近公共祖先不更新
}
int query(int x, int y) {
    while(top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    if (d[x] > d[y]) swap(x, y);
    return x;
}
void prim(int x) {
    priority_queue<pii<long long, pii<int, int>>> q;
    q.push(mp(0, mp(x, 0)));
    while(!q.empty() && cnt != n) {
        int qf = q.top().sc.fr;
        int ef = q.top().sc.sc;
        if (hs[qf]) {
            q.pop();
            continue;
        }
        cnt++;
        it[ef] = true;
        hs[qf] = true;
        ans -= q.top().fr;
        q.pop();
        for (int i = 0; i < v[qf].size(); ++i) {
            if (!hs[v[qf][i].sc.fr]) q.push(mp(-v[qf][i].fr, mp(v[qf][i].sc.fr, v[qf][i].sc.sc)));
        }
    }
}
//prim爱好者
void dfs1(int x, int p) {
    d[x] = d[p] + 1;
    f[x] = p;
    int maxson = -1;
    for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i].sc.fr;
        if (nx == p || !it[v[x][i].sc.sc]) continue;
        dfs1(nx, x);
        sz[x] += sz[nx];
        if (sz[nx] > maxson) {
            maxson = sz[nx];
            son[x] = nx;
        }
    }
    sz[x]++;
}
void dfs2(int x, int ntop) {
    id[x] = cnt;
    cnt++;
    top[x] = ntop;
    if (!son[x]) return;
    dfs2(son[x], ntop);
    for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i].sc.fr;
        if (nx == f[x] || nx == son[x] || !it[v[x][i].sc.sc]) continue;
        dfs2(nx, nx);
    }   
}
void dfs3(int x) {
    hs[x] = true;
    for (auto i : v[x]) {
        if (!hs[i.sc.fr]) dfs3(i.sc.fr);
        if (it[i.sc.sc]) continue;
        int fp = query(i.sc.fr, x);
        fchange(i.sc.fr, fp, i.fr);
        fchange(x, fp, i.fr);
    }
}
void dfs4(int x, int p) {
    for (auto i : v[x]) {
        if (!it[i.sc.sc]) continue;
        if (i.sc.sc == p) {
            fans[p] = ask(1, id[x], id[x]);
            if (fans[p] != LLONG_MAX) fans[p] = ans - i.fr + fans[p];
            continue;
        }
        dfs4(i.sc.fr, i.sc.sc);
    }
}

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        v[a].push_back(mp(c, mp(b, i)));       
        v[b].push_back(mp(c, mp(a, i)));
    }
    built(1, 1, n);//线段树
    prim(1);
    cnt = 1;
    dfs1(1, 0);
    dfs2(1, 1);
//dfs1和dfs2是树链剖分
    memset(hs, 0, sizeof(hs));
    dfs3(1);//遍历非树边并更新答案
    dfs4(1, 0);//统计答案并储存
    for (int i = 1; i <= m; ++i) {
        if (!it[i]) cout << ans << "\n";//非树边
        else if (fans[i] == LLONG_MAX) cout << "-1\n";//未被更新，是割边，无可替代
        else cout << fans[i] << "\n";
    }
    return 0;
}

一些更简洁方法的启发

不难发现，代码之所以冗长，主要就来自树链剖分加上线段树。那对于这种区间最小值的维护，是否存在更简单的方法？

考虑对每个节点维护一个小根堆，每一次小根堆里能够存储那些当前能用来做覆盖的权值。用类似树上差分的思想（非树边的两个端点的小根堆插入权值，两个端点的最近公共祖先删去两次该权值）， LCA 一次即可。注意合并时要用启发式合并。