简介

最近公共祖先是指在一个树或者有向无环图中同时拥有 x 和 y 作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果 y 是 x 的后代，那么 x 就是 x 和 y 的最近公共祖先。

如何求得两点 v 和 w 的最近公共祖先呢？或许我们可以用两次DFS求得根节点分别到两个点的路径，然后很轻松的求出两条路径的公共部分。
使用这个方法我们可以很容易的求出两点的最近公共祖先，时间复杂度为 O(n)，但如果需要 m 次查询，总复杂度达到了惊人的 O(nm)。下面来讨论一个时间复杂度更优的算法来解决这个问题。

倍增

顾名思义，倍增就是翻倍，把线性的处理转为对数级的处理。

先来看看另一种 O(n) 解LCA的思路：
令 dep[x] 为点 x 的深度, pre[x] 为点 x 的父节点

1. 如果 dep[x] > dep[y]，令 x=pre[x]，直到 dep[x]==dep[y]，此时点 x 与点 y 在同一层，如果 x==y，那么此时的点 x 就是两点的公共祖先。
2. 如果 x != y，那么令 x=pre[x]，y=pre[y]，点 x 与点 y 始终保持在同一深度，直到 x==y，此时的点 x 就是两点的公共祖先。

在上面的方法中，我们使点 x 与点 y 一步一步地向上跳直到 x==y，可以看出时间的花销都集中在向上跳的过程中，那有没有方法能优化跳的过程。

这时候该倍增法上场了：可知任意一个整数都能分解为2的幂次的和，那么对于一个高度 h，将其分解成
h = 2 ^ {a_1} + 2 ^ {a_2} + ... + 2 ^ {a_n}
这时候向上跳 n 步的过程变成了向上跳 log_2(n) 步的过程。

倍增求LCA

实现上述思路，即模拟向上跳 2^i 步的过程，需要进行简单的预处理。
细节看代码：【模板】最近公共祖先（LCA）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, s;
int pre[500010][20], dep[500010]; 

vector<int> son[500010];
void dfs(int u) {
    for(int i = 1; (1 << i) <= dep[u]; i++) { // 预处理pre数组
        pre[u][i] = pre[pre[u][i - 1]][i - 1];
    }
    for (auto v : son[u]) {
        if(dep[v]) continue;
        dep[v] = dep[u] + 1;
        pre[v][0] = u; //v的第2^0个祖先即为其父亲
        dfs(v);
    }
}

int lca(int x, int y) {
    if(dep[x] < dep[y]) {
        swap(x, y);
    }
    for(int i = 19; i >= 0; i--) { //从大到小枚举使x和y到了同一层
        if(dep[pre[x][i]] >= dep[y]) x = pre[x][i];
        if(x == y) return x;
    }
    for(int i = 19; i >= 0; i--) { //x, y同步向上跳
        if(pre[x][i] != pre[y][i]) { //无限接近公共祖先，但不能相遇
            x = pre[x][i];
            y = pre[y][i];
        }
    }
    return pre[x][0]; // 此时x, y均为其最小公共祖先的儿子
}

void run() {
    int x, y;
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        son[x].push_back(y);
        son[y].push_back(x);
    }
    dep[s] = 1; dfs(s);
    for(int i = 1; i <= m; i++) {
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(10);
    //int T = 1; cin >> T; while (T--)
    run();
}

预处理dfs需要 O(n) 的复杂度，接下来每次询问需要 O(logn) 的时间复杂度。
总复杂度 O(n + mlogn)