专栏文章

LCA

SSnowFlavour
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip230ya
此快照首次捕获于
2025/12/03 04:54
3 个月前
此快照最后确认于
2025/12/03 04:54
3 个月前
查看原文

一种求 LCA 的方法：RMQ\text{RMQ}

思路：一遍 DFS，求出节点的欧拉序。
然后每一次找出序列上两个点之间 dfn 最小的节点。

Code:

CPP
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 10;
int dfn[N], el[N << 1], dep[N], tot = 0;
int lg2[N << 1], fa[N << 1][25];
vector<int> e[N];
inline void dfs(int u, int fa) {
    el[dfn[u] = ++tot] = u;
    dep[u]             = dep[fa] + 1;
    for (auto v : e[u]) {
        if (v == fa) continue;
        // cout << u << " -> " << v << endl;
        dfs(v, u);
        el[++tot] = u;
    }
}
inline bool cmp(int x, int y) { return dep[x] < dep[y]; }
inline void init(int cnt) {
    for (int i = 2; i <= cnt; i++) lg2[i] = lg2[i >> 1] + 1;
    for (int i = 1; i <= cnt; i++) fa[i][0] = el[i];
    for (int j = 1; j <= lg2[cnt]; j++) {
        for (int i = 1; i + (1 << j) <= cnt; i++) {
            fa[i][j] = min(fa[i][j - 1], fa[i + (1 << (j - 1))][j - 1], cmp);
            // cout << fa[i][j] << endl;
        }
    }
}
inline int ask(int l, int r) {
    int H = lg2[r - l];
    return min(fa[l][H], fa[r - (1 << H)][H], cmp);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(s, 0);
    dep[0] = 1e9;
    init(tot);
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (u == v) {
            cout << u << endl;
            continue;
        }
        if (dfn[u] > dfn[v]) swap(u, v);
        cout << ask(dfn[u], dfn[v]) << endl;
    }
}

树上倍增：在 O(log⁡n)O(\log n) 时间内求解一系列链上问题

一般而言，序列上的 RMQ 是相对容易的，因为你可以通过 ST 表之类的东西进行维护。
链上问题就困难一些了，因为你没法弄到一种非常优秀的方法，给每个链都搞到一个数据结构。
除非你喜欢当 M 或者数据结构学傻了，你应该不会喜欢树剖吧……
因此，树上倍增就成为了一种简洁的求解链上问题的方法。
大部分的倍增都可以理解为用长度为 2i−12^{i-1} 的两个序列拼出一个 2i2^i 的序列。
有些时候，这个东西可以神秘：The Merchant.
CPP
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>

#pragma GCC optimize("Ofast")
#define endl      '\n'
#define min(x, y) (((x) < (y)) ? (x) : (y))
#define max(x, y) (((x) > (y)) ? (x) : (y))
// #define cin std::cin
// #define cout std::cout
// #define vector std::vector
// #define swap std::swap
// #define ios std::ios
using namespace std;
const int N = 5e4 + 10;
int fa[N][20], up[N][20], dw[N][20], mn[N][20], mx[N][20], w[N], dep[N],
    __lg[N];
namespace akioi {
inline int __lg(int x) { return ::__lg[x]; }
int n, fmin, fmax;
inline void init() {
    for (int i = 2; i <= n; i++) ::__lg[i] = ::__lg[i >> 1] + 1;
    int H = __lg(n);
    // w[0]  = 1e9;
    for (int i = 1; i <= n; i++) mn[i][0] = min(w[i], w[fa[i][0]]);
    // w[0] = 0;
    for (int i = 1; i <= n; i++) mx[i][0] = max(w[i], w[fa[i][0]]);
    for (int j = 1; j <= H; j++) {
        for (int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            int f    = fa[i][j - 1];
            mn[i][j] = min(mn[i][j - 1], mn[f][j - 1]);
            mx[i][j] = max(mx[i][j - 1], mx[f][j - 1]);
            up[i][j] = max(mx[f][j - 1] - mn[i][j - 1],
                           max(up[i][j - 1], up[f][j - 1]));
            dw[i][j] = max(mx[i][j - 1] - mn[f][j - 1],
                           max(dw[i][j - 1], dw[f][j - 1]));
            // cout << f << " " << mn[i][j] << " " << mx[i][j] << endl;
        }
        // cout << endl;
    }
}
inline int qup(int u, int f) {
    int H   = __lg(n);
    int ans = 0, nmin = w[u];
    for (int i = H; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[f]) {
            ans  = max(ans, max(up[u][i], mx[u][i] - nmin));
            nmin = min(nmin, mn[u][i]);
            u    = fa[u][i];
        }
    }
    fmin = nmin;
    return ans;
}
inline int qdw(int u, int f) {
    int H   = __lg(n);
    int ans = 0, nmax = w[u];
    for (int i = H; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[f]) {
            ans  = max(ans, max(dw[u][i], nmax - mn[u][i]));
            nmax = max(nmax, mx[u][i]);
            u    = fa[u][i];
        }
    }
    fmax = nmax;
    return ans;
}
vector<int> e[N];
struct node {
    int u, fa;
};
inline void dfs(int u, int fa) {
    stack<node> st;
    node nw;
    nw.u  = u;
    nw.fa = fa;
    st.push(nw);
    while (!st.empty()) {
        nw = st.top();
        st.pop();
        int fa = nw.fa, u = nw.u;
        ::fa[u][0] = fa;
        dep[u]     = dep[fa] + 1;
        for (int i = 0; i < e[u].size(); i++) {
            int v = e[u][i];
            if (v == fa) continue;
            nw.u  = v;
            nw.fa = u;
        // cerr << u << " " << v << endl;
            st.push(nw);
        }
    }
}
inline int LCA(int u, int v) {
    int H = __lg(n);
    if (dep[v] > dep[u]) swap(u, v);
    for (int i = H; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if (u == v) return u;
    for (int i = H; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    }
    return fa[u][0];
}
} // namespace akioi
int main() {
    // freopen("test.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> akioi::n;
    // cerr << __LINE__ << endl;
    for (int i = 1; i <= akioi::n; i++) cin >> w[i];
    for (int i = 1; i < akioi::n; i++) {
        int u, v;
        cin >> u >> v;
        akioi::e[u].push_back(v);
        akioi::e[v].push_back(u);
    }
    // cerr << __LINE__ << endl;
    akioi::dfs(1, 0);
    // cerr << __LINE__ << endl;
    akioi::init();
    // cerr << __LINE__ << endl;
    // cout << akioi::__lg(1024) << endl;
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        int l  = akioi::LCA(u, v);
        int up = akioi::qup(u, l);
        int dw = akioi::qdw(v, l);
        // cout << up << " " << dw << " " << fmax << " " << fmin << endl;
        cout << max(akioi::fmax - akioi::fmin, max(up, dw)) << endl;
    }
}
（本题卡常，而我的代码常数太大，所以你就看到我的 DFS 是怎么写的了。）

树上差分

就是记录从这个节点到根的路径上，每一个节点的权值都加上某个数（也不一定是加，乘除什么的都行）。
听上去老简单了，如果要给一条链增加一些东西，则：
  1. 如果是要给路径的点，这个比较容易理解，将 uu 和 vv 加上 xx，这样 LCA(u,v)\text{LCA}(u, v) 以及它的所有父亲都被算了两次，我们要给 LCA\text{LCA} 减去 xx，给 LCA\text{LCA} 的父亲再减去 xx。
  2. 如果是要给路径的边，我们一般用这条边的儿子端来代表这条边。此时我们给 uu 和 vv 加上 xx，然后直接给 LCA(u,v)\text{LCA}(u,v) 减去 xx 即可。
模板略，这些例题比较有意思：

疫情控制

这玩意就是二分时间，然后让能跳的可着劲往上跳（因为显然跳到根节点的儿子是不劣于待在原地的），然后如果一个军队到了根节点就没法守家了（也就是说，他到了根节点就没有时间回来了），那么他就不如待在自己家（因为他就算能支援，也只能支援那些距离根节点比他近的，而如果他压根不离开，就等效于他出去又回来，走了更多的路。）
代码非常好写.jpg
CPP
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
struct edge {
    int v, w;
};
vector<edge> e[N];
using ll = long long;
int fa[N][20], n, m, loc[N], bel[N], jp[N];
ll dis[N][20], dst[N];
bool vis[N];
inline void init() {
    int H = __lg(n);
    for (int j = 1; j <= H; j++) {
        for (int i = 1; i <= n; i++) {
            fa[i][j]  = fa[fa[i][j - 1]][j - 1];
            dis[i][j] = dis[i][j - 1] + dis[fa[i][j - 1]][j - 1];
        }
    }
}
inline void dfs1(int u, int fa, int c) {
    // cout << u << " " << fa << endl;
    dis[u][0]  = c;
    ::fa[u][0] = fa;
    for (auto p : e[u]) {
        int v = p.v, w = p.w;
        if (v == fa) continue;
        dfs1(v, u, w);
    }
}
inline bool dfs2(int u, int fa) {
    if (vis[u] && (fa - 1)) return 1;
    bool ans = (e[u].size() - 1);
    for (auto p : e[u]) {
        int v = p.v;
        if (v == fa) continue;
        ans &= dfs2(v, u);
        if (!ans) return false;
    }
    return ans;
}
// #define debug
inline bool check(ll x) {
#ifdef debug
    cout << "# " << x << endl;
#endif
    memset(vis, 0, sizeof(vis));
    vector<int> reach, req;
    vector<bool> prt(N), rp(N);
    int H = __lg(n);
    for (int i = 1; i <= m; i++) {
        if (dst[loc[i]] <= x) {
            int u = jp[loc[i]] = bel[loc[i]];
            if (dst[loc[i]] + 2 * dis[bel[loc[i]]][0] > x) rp[u] = prt[u] = 1;
        } else {
            int u = loc[i], nx = x;
            for (int i = H; i >= 0; i--) {
                if (dis[u][i] <= nx) nx -= dis[u][i], u = fa[u][i];
            }
            jp[loc[i]] = u;
        }
        vis[jp[loc[i]]] = 1;

        // cout << jp[loc[i]] << " ";
    }
    // cout << endl;
    for (auto p : e[1]) {
        if (prt[p.v]) continue;
        bool pt = dfs2(p.v, fa[p.v][0]);
        if (pt) prt[p.v] = 1;
        else req.push_back(p.v);
    }
    for (int i = 1; i <= m; i++)
        if ((!rp[bel[loc[i]]] && prt[bel[loc[i]]]) ||
            dst[loc[i]] + 2 * dis[bel[loc[i]]][0] <= x) {
            reach.push_back(loc[i]);
        } else prt[bel[loc[i]]] = 1, rp[bel[loc[i]]] = 0;
    sort(reach.begin(), reach.end(), [](int a, int b) {
        return (dst[a] + dis[bel[a]][0] > dst[b] + dis[bel[b]][0]);
    });
    sort(req.begin(), req.end(),
         [](int a, int b) { return dis[a][0] < dis[b][0]; });
    auto p = reach.begin();
#ifdef debug
    cout << "Reach:";
    for (auto p : reach) cout << p << " ";
    cout << endl;
    cout << "Req:";
    for (auto p : req) cout << p << " ";
    cout << endl;
#endif
    for (auto u : req) {
        bool ok = 0;
        for (; p != reach.end(); p++) {
            ll len = dis[bel[*p]][0] + dis[u][0];
            if (x - dst[*p] >= len) {
                ok = 1;
#ifdef debug
                cout << "Match:" << *p << " " << u << " " << len << endl;
#endif
                ++p;
                break;
            }
        }
        if (!ok) return 0;
    }
    return 1;
}
int main() {
    // freopen("P1084_7.in", "r", stdin);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((edge){v, w});
        e[v].push_back((edge){u, w});
    }
    sort(e[1].begin(), e[1].end(), [](edge x, edge y) { return x.w < y.w; });
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> loc[i], vis[loc[i]] = 1;
    dfs1(1, 0, 0);
    init();
    int H = __lg(n);
    for (int i = 1; i <= n; i++) {
        int u = i;
        for (int j = H; j >= 0; j--) {
            if (fa[u][j] > 1) dst[i] += dis[u][j], u = fa[u][j];
        }
        // cout << fa[9][0] << " " << fa[9][1] << endl;
        // cout << i << " " << dst[i] << endl;
        bel[i] = u;
    }
    sort(loc + 1, loc + 1 + m, [](int x, int y) { return dst[x] > dst[y]; });
    ll l = 0, r = 1e15;
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (l != 1e15) cout << l << endl;
    else cout << -1 << endl;
}

天天爱跑步

这个就是一个经典的套路：对于某种会以某种恒定的方式动的东西，我们记录一些不会变的东西，就可以确定他的状态。
比如说，我有一个箱子，在 ii 秒在 xx 位置出现，以 1m/s1m/s 的速度在向右运动，那么我们就可以将它看作一个第 00 秒从 x−ix-i 位置出现的箱子，但是这个箱子只存在于 xx 向右的位置。
有了这一点，这个问题就比较简单了。
这个代码至少比上一个简单。
CPP
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e6 + 10, PY = 6e5 + 10;
vector<int> e[N], add[N][2], del[N][2];
int fa[N][30], dep[N], w[N], n, m;
int cnt[N][2], ans[N];
inline void init() {
    int H = __lg(n);
    for (int j = 1; j <= H; j++) {
        for (int i = 1; i <= n; i++) { fa[i][j] = fa[fa[i][j - 1]][j - 1]; }
    }
}
inline void dfs1(int u, int fa) {
    ::fa[u][0] = fa;
    dep[u]     = dep[fa] + 1;
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs1(v, u);
    }
}
inline int LCA(int x, int y) {
    int H = __lg(n);
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = H; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    }
    if (x == y) return x;
    for (int i = H; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
inline void dfs2(int u, int fa) {
    int beg1 = 0, beg2 = 0;
    beg1 = cnt[dep[u] + w[u]][0];
    beg2 = cnt[w[u] - dep[u] + PY][1];
    for (auto v : del[u][0]) cnt[v][0]--;
    for (auto v : del[u][1]) cnt[v][1]--;
    for (auto v : add[u][0]) cnt[v][0]++;
    for (auto v : add[u][1]) cnt[v][1]++;
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs2(v, u);
    }
    ans[u] = cnt[dep[u] + w[u]][0] - beg1;
    ans[u] += cnt[w[u] - dep[u] + PY][1] - beg2;
    // cout << u << endl;
    // for (int i = -n; i <= n; i++) cout << cnt[i + PY][1] << " ";
    // cout << endl;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> w[i];
    dfs1(1, 0);
    init();
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int l = LCA(v, u);
        add[u][0].push_back(dep[u]);
        del[fa[l][0]][0].push_back(dep[u]);
        add[v][1].push_back(dep[u] - 2 * dep[l] + PY);
        del[l][1].push_back(dep[u] - 2 * dep[l] + PY);
    }
    dfs2(1, 0);
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...