简介
LCA是一种树上问题，为求两个点之间的最近公共祖先。
最近公共祖先就是往上走到最近的点，使得这个点是另两个点的祖先。
模板题
可以看洛谷上的模板题：P3379 【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 \(N\)，\(M\)，\(S\)，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 \(N-1\) 行每行包含两个正整数 \(x\)，\(y\) 表示 \(x\) 结点和 \(y\) 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 \(M\) 行每行包含两个正整数 \(a\)，\(b\) 表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。
输出格式
输出包含 \(M\) 行，每行包含一个正整数，依次为每一个询问的结果。
输入样例
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出样例
4
4
1
4
4
暴力
直接想让其中一个点往上走，直到两个点深度相同，再两个点一起往上走，直到重合，重合的点即为最近公共祖先
倍增
如果两个点相隔很远，那么要走好多步才能深度相同或重合。
那么需要用到倍增的思想，这里包含 \(dp\) 的思想。
倍增算法即在往上走是先走 \(2^k\) 步，再走常数步到达最近公共祖先，这样可以加快其速度，并优化暴力算法。
对于求出深度，我们可以使用 dfs：
void dfs(int to, int fa) {
f[to][0] = fa; dep[to] = dep[fa] + 1;
for(int i = 1; i <= lg[dep[to]]; i++) f[to][i] = f[f[to][i - 1]][i - 1];
for(int i = 0; i < g[to].size(); i++) if(g[to][i] != fa) dfs(g[to][i], to);
}
\(f_{i,j}\) 表示第 \(i\) 个点往上走 \(2^j\) 步到达的点，则有
\[f_{i,j} = f_{f_{i, j-1}, j-1} \]我们可以从大到小枚举 \(k\)，第一个相同的深度再跳到下一层即为最近公共祖先
for(int k = lg[dep[x]] - 1; k >= 0; k--)
if(f[x][k] != f[y][k]) x = f[x][k], y = f[y][k];
这是LCA模板题完整的代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int n, m, s;
vector<int> g[MAXN];
int dep[MAXN], f[MAXN][22], lg[MAXN];
void dfs(int to, int fa) {
f[to][0] = fa; dep[to] = dep[fa] + 1;
for(int i = 1; i <= lg[dep[to]]; i++) f[to][i] = f[f[to][i - 1]][i - 1];
for(int i = 0; i < g[to].size(); i++) if(g[to][i] != fa) dfs(g[to][i], to);
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
while(dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]] - 1];
if(x == y) return x;
for(int k = lg[dep[x]] - 1; k >= 0; k--)
if(f[x][k] != f[y][k]) x = f[x][k], y = f[y][k];
return f[x][0];
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= n; i++) lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
dfs(s, 0);
for(int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}