板子 LCA

倍增法、重链剖分、ST 表求树上公共祖先。

倍增法

时间复杂度：预处理 \(\mathcal O(n\log n)\)，单次查询 \(\mathcal O(\log n)\)；

空间复杂度：\(\mathcal O(n\log n)\)。

int deep[N], fa[N][20];
void dfs(int u, int pre) {
    deep[x] = deep[pre] + 1;
    fa[u][0] = pre;
    for (int i = 1; i <= 19; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = G.head[u]; i; i = G.nxt[i]) {
    	int v = G.to[i];
        if (v == pre) continue;
        dfs(v, u);
    }
}
inline int LCA(int a, int b) {
    if (deep[a] < deep[b]) swap(a, b);
    for (int i = 19; ~i; --i)
        if (deep[fa[a][i]] >= deep[b])
            a = fa[a][i];
    for (int i = 19; ~i; --i)
        if (fa[a][i] != fa[b][i])
            a = fa[a][i], b = fa[b][i];
    return a == b ? a : fa[a][0];
}

重链剖分

时间复杂度：预处理 \(\mathcal O(n)\)，单次查询 \(\mathcal O(\log n)\)；

空间复杂度：\(\mathcal O(n)\)。

很多时候比倍增快一点。

int deep[N], fa[N], top[N], size[N], son[N];
void dfs1(int u, int pre) {
    fa[u] = pre;
    deep[u] = deep[pre] + 1;
    size[u] = 1;
    for (int i = G.head[u]; i; i = G.nxt[i]) {
        int v = G.to[i];
        if (v == pre) continue;
        dfs1(v, u);
        size[u] += size[v];
        if (!son[u] || size[v] > size[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp) {
    top[u] = tp;
    if (!son[u]) return;
    dfs2(son[u], tp);
    for (int i = G.head[u]; i; i = G.nxt[i]) {
        int v = G.to[i];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
inline int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return deep[x] < deep[y] ? x : y;
}

ST 表

时间复杂度：预处理 \(\mathcal O(n\log n)\)，单次查询 \(\mathcal O(1)\)；

空间复杂度：\(\mathcal O(n\log n)\)。

注意 \(tot\) 为 \(n\) 的两倍。

int tot;
int st[N * 4][20], log[N * 2], deep[N], aa[N * 2], fir[N];
void dfs(int u, int fa) {
    deep[u] = deep[fa] + 1;
    aa[++tot] = u;
    fir[u] = tot;
    for (int i = G.head[u]; i; i = G.nxt[i]) {
        int v = G.to[i];
        if (v == fa) continue;
        dfs(v, u);
        aa[++tot] = u;
    }
}
inline void init() {
    dfs(1, 0);
    log[0] = -1;
    for (int i = 1; i <= tot; ++i) log[i] = log[i >> 1] + 1;
    for (int i = 1; i <= tot; ++i) st[i][0] = aa[i];
    for (int i = 1; i <= 19; ++i) {
        for (int u = 1; u <= tot; ++u) {
            int x = st[u][i - 1], y = st[u + (1 << (i - 1))][i - 1];
            st[u][i] = deep[x] < deep[y] ? x : y;
        }
    }
}
inline int LCA(int x, int y) {
    int l = fir[x], r = fir[y];
    if (l > r) swap(l, r);
    int lo = log[r - l + 1];
    int t1 = st[l][lo], t2 = st[r - (1 << lo) + 1][lo];
    return deep[t1] < deep[t2] ? t1 : t2;
}