本次讨论树这种数据结构上的一种算法—用倍增算法求最近公共祖先(LCA)。

首先介绍倍增算法的原理。
        若给定一个正整数x且有x < 2k，若从2k开始，令x从大到小依次减去2的方幂p(2k，2k-1…，1)，第一个能够使x-p≥0的数p必定在数x的二进制拆分表达式中。这个很容易用二进制解释证明。
        用depth[]储存每一个节点的深度(认为根节点深度为1)，用grand[][]储存每个节点的祖先并定义grand[x][y]表示x节点向上2y处的祖先。若越界则置为0。显然grand[x][0]是每个节点的父节点编号。这两个数组均可由DFS求出，详见示例代码。
        给定两个待求LCA的节点标号，首先要做的是将两个节点排到同一深度。操作方法是令深度较大的节点向上”跳跃”，直至深度与较小节点相同。一种朴素的方法是一层一层地向上跳，但时间消耗明显。这里可以用与快速幂类似的倍增思想加快跳跃速度。
        首先确定k的大小，容易知道k=ceil{log_2(DEPTH)}，这里DEPTH为树的最大深度。通常取20即可。从大到小枚举2的方幂p，最终能使较大深度节点达到与较小深度节点相同的深度。这时如果两个节点重合，则它即为LCA。
        若两个节点不相同，就需要让这两个节点同时向上跳，加快跳跃速度的方式与之前类似，也是通过倍增实现，跳跃后会到达LCA的正下方，直接返回父节点即可。

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
70
71
72
#include<cstring>
#include<cstdio>
#include<iostream>

using namespace std;
const int MAX = 500001;
struct edge {//链式前向星存边
    int to, next;
} op[MAX * 2];
int head[MAX];//链式前向星节点首边
int cnt = 0;//边编号
int root = 1;//根节点编号
int depth[MAX] = {0};//存各个节点深度
int grand[MAX][21] = {0};//倍增使用
int N, M;//存节点数和询问数

int read() {//读入优化
    char e = static_cast<char>(getchar());
    while (e < '0' || e > '9')e = static_cast<char>(getchar());
    int sum = 0;
    while (e >= '0' && e <= '9') {
        sum *= 10, sum += e - '0';
        e = static_cast<char>(getchar());
    }
    return sum;
}

void add(int x, int y) {//构建链式前向星,从x到y有一条边
    op[cnt].to = y;
    op[cnt].next = head[x];
    head[x] = cnt++;
}

void DFS(int x) {
    for (int i = head[x]; i != -1; i = op[i].next) {//遍历各个子节点
        if (depth[op[i].to] != 0)continue;//不能向父节点回溯
        depth[op[i].to] = depth[x] + 1;//深度加一
        grand[op[i].to][0] = x;//初始化递推
        for (int j = 1; j < 21; j++)grand[op[i].to][j] = grand[grand[op[i].to][j - 1]][j - 1];//递推
        DFS(op[i].to);//下一个子节点
    }
}

int LCA(int x, int y) {//求LCA的函数
    if (depth[x] > depth[y])swap(x, y);//认为y的深度较大
    for (int i = 20; i >= 0; i--) {
        if (depth[grand[y][i]] >= depth[x])y = grand[y][i];//y倍增至与x同深度
    }
    if (x == y)return x;//节点相同就是LCA 直接返回
    for (int i = 20; i >= 0; i--) {//两个节点倍增至LCA的正下方
        if (grand[x][i] != grand[y][i])x = grand[x][i], y = grand[y][i];
    }
    return grand[x][0];//父节点即为LCA
}

int main() {
    N = read(), M = read(), root = read();
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= N - 1; i++) {
        int x, y;
        x = read(), y = read();
        add(x, y), add(y, x);
    }//读入树的信息
    depth[root] = 1;//初始化
    DFS(root);//深搜求depth和grand
    for (int i = 0; i < M; i++) {
        int x, y;
        x = read(), y = read();
        printf("%d\n", LCA(x, y));
    }
    return 0;
}