dfs序O(1)判断祖孙关系

#include <bits/stdc++.h>

using namespace std;

const int N = 4e4 + 10;

int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
int tim, dfn[N], siz[N];
int root;

void addedge(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int f) {
    siz[u] = 1;
    dfn[u] = ++ tim;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == f) continue;
        dfs(j, u);
        siz[u] += siz[j];
    }
    return;
}

int main(void) {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        else {
            addedge(a, b), addedge(b, a);
        }
    }

    dfs(root, root);

    cin >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        if (dfn[b] <= dfn[a] + siz[a] - 1 && dfn[a] <= dfn[b]) puts("1");
        else if (dfn[a] <= dfn[b] + siz[b] - 1 && dfn[b] <= dfn[a]) puts("2");
        else puts("0");
    }
    return 0;
}

树链剖分求LCA(跑的更快，个人感觉更好写)

#include <bits/stdc++.h>

using namespace std;

const int N = 4e4 + 10;

int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
int dep[N], fa[N], siz[N], son[N], tim, dfn[N], top[N];
int root;

void addedge(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    int maxsize = -1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == f) continue;
        dfs1(j, u);
        siz[u] += siz[j];
        if (siz[j] > maxsize) {
            maxsize = siz[j];
            son[u] = j;
        }
    }
    return;
}

void dfs2(int u, int t) {
    dfn[u] = ++tim;
    top[u] = t;
    if (!son[u]) {
        return;
    }
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
    return;
}

int main(void) {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        else {
            addedge(a, b), addedge(b, a);
        }
    }

    dfs1(root, root);
    dfs2(root, root);

    cin >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        int x = a, y = b, f;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {swap(x, y);}
            x = fa[top[x]];
        }
        f = (dep[x] < dep[y]) ? x : y;
        if (f == a) cout << "1\n";
        else if (f == b) cout << "2\n";
        else cout << "0\n";
    }
    return 0;
}

倍增求LCA

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];
int q[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int root) {
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> q;
    q.push(root);
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for (int k = 1; k <= 15; k ++ ) 
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- ) {
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
        }
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- ) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

int main(void) {
    cin >> n;

    int root = 0;
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i ++ ) {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }

    bfs(root);

    cin >> m;
    for (int i = 1; i <= m; i ++ ) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }

    return 0;
}