7 树论

7.1 树上倍增

LCA、树上路径、树上路径边权最值。

constexpr int N = 1e5 + 5;
int dep[N], fa[20][N]; // 2^20 = 1048576
vector<vector<int>> g(N);
void dfs(int x, int f) {
    dep[x] = dep[f] + 1, fa[0][x] = f;
    for (int i = 1; i < 20; ++i)
        fa[i][x] = fa[i-1][fa[i-1][x]];
    for (int y : g[x])
        if (y != f) dfs(y, x);
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 19; ~i; --i)
        if (dep[fa[i][x]] >= dep[y]) x = fa[i][x];
    if (x == y) return y;
    for (int i = 19; ~i; --i)
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}

7.2 dfs序LCA

\(O(n\log{n})\) 预处理，\(O(1)\) 查询。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
constexpr int K = __lg(N) + 3;
int n, m, s;
int dfn[N], cnt, st[K][N]; 
vector<vector<int>> g(N);
void dfs(int x, int f) {
    dfn[x] = ++cnt;
    st[0][dfn[x]] = f;
    for (int y : g[x])
        if (y != f) dfs(y, x);
}
void build_lca() {
    for (int j = 1; j < K; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int p1 = st[j-1][i];
            int p2 = st[j-1][i + (1 << (j-1))];
            st[j][i] = dfn[p1] < dfn[p2] ? p1 : p2;
        }
    }
}
int lca(int x, int y) {
    if (x == y) return x;
    if (dfn[x] > dfn[y]) swap(x, y);
    int j = __lg(dfn[y] - dfn[x]);
    int p1 = st[j][dfn[x]+1];
    int p2 = st[j][dfn[y]-(1<<j)+1];
    return dfn[p1] < dfn[p2] ? p1 : p2; 
}
signed main() {
    dfs(s, 0); // s 是根
    build_lca();
    cout << lca(u, v);
}

7.3 虚树

当查询点总数有限时，根据查询点及其LCA建立虚树，然后在虚树上面dp。需要预处理LCA和dfs序。

vector<int> g[N], h[N], used; // 原树、虚树、虚树中用到的点
int stk[N], top;

void add_edge(int x, int y) {
    h[x].emplace_back(y);
    used.emplace_back(x);
}

void clear() {
    for (int x : used) {
        h[x].clear();
    }
    used.clear();
}

void build() {
    sort(a+1,a+1+k,[&](int x, int y) {
        return dfn[x] < dfn[y];
    });
    stk[top=1] = 1;
    if (a[1] != 1) stk[++top] = a[1];
    for (int i = 2; i <= k; i++) {
        int c = lca(stk[top], a[i]);
        while (top > 1 and dep[stk[top-1]] >= dep[c]) {
            add_edge(stk[top-1], stk[top]);
            top--;
        }        
        if (c != stk[top]) {
            add_edge(c, stk[top]);
            stk[top] = c;
        }
        stk[++top] = a[i];
    }
    while (top > 1) {
        add_edge(stk[top-1], stk[top]);
        top--;
    }
}