最近公共祖先（LCA)

问题场景

给定一颗无向树，并且给出树中任意两个结点，要求求出这两个节点的最近公共祖先。

倍增法

1.DFS初始化

这里直接说解决方法，推荐使用倍增法，原理和跳表(Skiplist)大致相似。原理是使用一个数组，father[i][j]，含义是结点i的第个父节点。

（1）父节点处理

和跳表类似，其实对于每个节点，我们开个大小为31的father[i][31]一般就够用了，其实使用幂乘运算很显然，$2^j=2{j-1}\times2^{j-1}2j$个父节点等于 {a的第$2^{j-1}2{j-1}$个父节点}**。 这句话直接看的话可能不太直观，下面是代码描述：

for(int i=1;i<31;i++){
 father[root][i]=father[father[root][i-1]][i-1];
}

（2）计算每个节点的深度

不过只知道每个节点的父节点还不够，如果要求LCA，还需要知道每个节点相对于根节点的深度depth[i]。这个简单，只需要在dfs的时候记录一下就可以了。

2.调整深度寻找LCA

（1）求解深度差，将两个结点置于同一深度

这里的做法是首先求出深度差，比如差值为7，那么转成二进制就是00000111,那么对于较深的那个节点a，有以下几条步骤：

1. 第一步，走一步，找到a的父节点b；
2. 第二步，走两步，找到b的第个父节点c；
3. 第三步，走四步，找到c的第个父节点d。
   这样一来，最终找到的节点d与a的深度差一定是：。目标达成。

（2）遍历父节点，直到两个结点变成LCA的两个不同儿子

做完第一步有两种情况，情况1是我们刚好找到了LCA，如下图：

这种情况就非常幸运了，直接返回这个节点就可以了。

不过，情况2更为常见，就是我们找到的x和y其实是深度相同的不同节点。

那么这种情况下，还是需要继续遍历的，此时的a就是刚才find的那个‘7’。我们直接从最大的j=30开始遍历，那么因为这个数字很大，所以一开始father[a][30]和father[b][30]一定都是相同的。

不断减小j，如果减小到一定程度,搞好father[a][j]和father[b][j]不相同，那么就可以进一步缩小范围，更新 a=father[a][j]，b=father[b][j]。直接进一步减少j，直到找到最接近LCA的两个不同的a和b。

Note

Question:为什么这里第一次找到不同的father[a][j]和father[b][j]时不能break？

这里非常推荐使用二进制的方式回答这个问题。我们可以回顾求深度差的那个部分，现实中非常有可能出现的情况是，LCA和a的深度差并不是2的整数幂！！！

比如LCA距离a的深度差为23，化成二进制就是10101，如果只跳一次就是16，就是10000，所以还是需要继续寻找更小的j的，这里不能就在第一次的时候就break！！

完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
const int LOGN = 20;

vector<int> adj[MAXN];
int fa[MAXN][LOGN], dep[MAXN];

void dfs(int node, int parent) {
    fa[node][0] = parent;
    dep[node] = dep[parent] + 1;
    for (int i = 1; i < LOGN; i++) {
        fa[node][i] = fa[fa[node][i-1]][i-1];
    }
    // 每个节点都连接着自己的父节点，加上此句避免重复访问
    for (int child : adj[node]) {
        if (child != parent) {
            dfs(child, node);
        }
    }
}

void preprocess(int root) {
    dep[root] = 0;
    dfs(root, 0);
}

int lca(int x, int y) {
  // 令 y 比 x 深。
  if (dep[x] > dep[y]) swap(x, y);
  // 令 y 和 x 在一个深度。
  int tmp = dep[y] - dep[x];
  // 根据深度差的二进制值选择y的父节点，保证y和x的深度是相同的
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) y = fa[y][j];
  // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
  if (y == x) return y;
  // 不然的话，找到第一个不是它们祖先的两个点。
  // (人话) 也就是找到LCA儿子中的任意两个不同点
  for (int j = 30; j >= 0 && y != x; --j) {
    // 只要是不同点，每次都保存
    if (fa[x][j] != fa[y][j]) {
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // 此时x和y已经是LCA中的两个不同节点了，那么它们两的直接父亲一定就是LCA
  return father[x][0];
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    preprocess(1); // 假设1是根节点
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}