题目来自洛谷P3379 【模板】最近公共祖先（LCA）
【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 \(N,M,S\)，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 \(N-1\) 行每行包含两个正整数 \(x, y\)，表示 \(x\) 结点和 \(y\) 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 \(M\) 行每行包含两个正整数 \(a, b\)，表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。
输出格式
输出包含 \(M\) 行，每行包含一个正整数，依次为每一个询问的结果。
样例 #1
样例输入 #1
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
样例输出 #1
4
4
1
4
4
提示
对于 \(30\%\) 的数据，\(N\leq 10\)，\(M\leq 10\)。
对于 \(70\%\) 的数据，\(N\leq 10000\)，\(M\leq 10000\)。
对于 \(100\%\) 的数据，\(1 \leq N,M\leq 500000\)，\(1 \leq x, y,a ,b \leq N\)，不保证 \(a \neq b\)。
样例说明：
该树结构如下：
第一次询问：\(2, 4\) 的最近公共祖先，故为 \(4\)。
第二次询问：\(3, 2\) 的最近公共祖先，故为 \(4\)。
第三次询问：\(3, 5\) 的最近公共祖先，故为 \(1\)。
第四次询问：\(1, 2\) 的最近公共祖先，故为 \(4\)。
第五次询问：\(4, 5\) 的最近公共祖先，故为 \(4\)。
故输出依次为 \(4, 4, 1, 4, 4\)。
2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。
最近公共祖先——树上倍增
预处理（倍增） \(O(nlogn)\)
\(fa[i, j]\)表示从\(i\)结点出发，向上跳\(2^j\)步所抵达的节点编号；
求解方式:
\(j = 0, fa[i, 0] = i的父节点\)
\(j > 0\), \(i\)向上跳\(2^{i-1}\)步后再跳\(2^{i-1}\)步就可以跳到\(2^i\)的位置，所以\(\forall 0 < j \leq Max\)，$$fa[i, j] = fa[fa[i, j-1], j-1]$$
\(depth[i]\)表示结点\(i\)的深度；
哨兵: \(depth[0] = 0; fa[i, j]=0\), 表示\(i\)向上跳\(2^j\)步跳出根结点的范围。
实现方式: \(DFS或BFS\)
查询 \(O(log n)\)
查询分两步走：
（\(1\)）先将两个点跳到同一层
该步骤可以使用二进制拼凑的方式来实现。假设\(depth[x] > depth[y]\)，则两者之间的差距为\(k = depth[x] - depth[y]\)，由于是按照\(2\)的整数幂向上跳，所以可以通过取\(k\)的二进制表示中\(1\)所在的位对应的权值进行跳跃即可将\(x\)跳到与\(y\)同一层。
在实现过程中，可以从大到小枚举指数\(e\)，当\(depth[fa[x][e]] >= depth[y]\)时，\(x=fa[x][e]\), 这样当\(x\)跳到与\(y\)同一层时就会停止跳跃。
如果在这一步后\(x == y\), 则直接返回\(x\).
（\(2\)）两个点同时向上跳，直到跳到最近公共祖先的下一层
为什么是下一层？因为如果直接判断是否跳到同一个节点，无法判断是否为最近的公共祖先，而有可能只是一个公共祖先。
判断条件: 从大到小枚举指数\(i\), \(fa[x, i] \neq fa[y, i]\), \(x = fa[x, i], \, y = fa[y, i]\)。
当\(fa[x, i] == fa[y, i]\)时，证明此时\(x, y\)已经跳到了最近公共祖先的下一层, 此时\(f[x][0]\)或\(f[y][0]\)就是答案。
#include<bits/stdc++.h>
const int N = 500050;
int n, m, s;
std::vector<std::vector<int>> g(N);
int f[N][22];
int depth[N];
void pre(int root){
memset(depth, 0x3f, sizeof depth);
std::queue<int> q;
q.push(root);
depth[root] = 1;
depth[0] = 0;
while(!q.empty()){
auto u = q.front();
q.pop();
for(auto v:g[u]){
if(depth[v] > depth[u] + 1){
depth[v] = depth[u] + 1;
f[v][0] = u;
q.push(v);
for(int k = 1; k <= 20; k ++ ){
f[v][k] = f[f[v][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b){
if(depth[a] < depth[b]) std::swap(a, b);
for(int k = 20; k >= 0; k -- ){
if(depth[f[a][k]] >= depth[b]){
a = f[a][k];
}
}
if(a == b) return a;
for(int k = 20; k >= 0; k -- ){
if(f[a][k] != f[b][k]){
a = f[a][k];
b = f[b][k];
}
}
return f[a][0];
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> n >> m >> s;
for(int i = 0; i < n - 1; i ++ ){
int x, y;
std::cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
pre(s);
while(m -- ){
int a, b;
std::cin >> a >> b;
int anc = lca(a, b);
std::cout << anc << '\n';
}
return 0;
}