LCA 板子（最近公共祖先）

树上倍增法
预处理O(nlogn)，每次询问O(logn)

预处理bfs（宽搜不容易因为递归层数过多爆栈）
1、从root开始
2、所有depth初始化正无穷，哨兵depth[0] = 0, depth[root] = 1
3、遍历子节点时，如果depth大于更新，说明没有被搜索过，更新depth，放入队列，更新fa数组，fa[v][0]就是它的2^0也就是父节点，然后循环k[1,15]更新fa

通过预处理bfs我们得到了depth数组和fa[i][j]（节点i的2^j辈祖先）数组

询问lca
1、假设x是更深的那个
2、x往上跳，k[15,0]，二进制拼凑，如果x跳了当前的k还是大于等于y的深度，就跳，否则不跳且continue
3、现在x和y同一深度了，如果x=y，说明y是x和y的lca，return x
4、否则，x和y一起往上跳，k[15,0]，结果是要一起跳到lca的下一层；如果x和y的2^k辈祖先不相同，则跳；否则不跳，continue
5、循环结束后，x的父节点就是lca了

#include 
#include 
#include 
#include 
using namespace std;
const int N = 4e4 + 10;

int n, m;
vector<int> g[N];
int depth[N];
int fa[N][16];

void bfs(int root) {
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0;
    depth[root] = 1;
    queue<int> que;
    que.push(root);
    while (que.size()) {
        int t = que.front(); que.pop();
        for (int v : g[t]) {
            if (depth[v] > depth[t] + 1) {
                depth[v] = depth[t] + 1;
                que.push(v);
                fa[v][0] = t;
                for (int k = 1; k <= 15; ++ k) {
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
                }
            }
        }
    }
}
int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 15; k >= 0; -- k) {
        if (depth[fa[x][k]] >= depth[y]) {
            x = fa[x][k];
        }
    }
    if (x == y) return x;
    for (int k = 15; k >= 0; -- k) {
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}

int main() {
    cin >> n;
    int root;
    for (int i = 0, a, b; i < n; ++ i) {
        cin >> a >> b;
        if (b == -1) root = a;
        else g[a].push_back(b), g[b].push_back(a);
    }
    bfs(root);
    cin >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        int pa = lca(a, b);
        if (pa == a) cout << 1 << endl;
        else if (pa == b) cout << 2 << endl;
        else cout << 0 << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69