简介
LCA是一种树上问题，为求两个点之间的最近公共祖先。
最近公共祖先就是往上走到最近的点，使得这个点是另两个点的祖先。
模板题
可以看洛谷上的模板题：P3379 【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 $N$，$M$，$S$，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 $N-1$ 行每行包含两个正整数 $x$，$y$ 表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 $M$ 行每行包含两个正整数 $a$，$b$ 表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。
输出格式
输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。
输入样例
1
2
3
4
5
6
7
8
9
10
| 5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
|
输出样例
暴力
直接想让其中一个点往上走，直到两个点深度相同，再两个点一起往上走，直到重合，重合的点即为最近公共祖先
倍增
如果两个点相隔很远，那么要走好多步才能深度相同或重合。
那么需要用到倍增的思想，这里包含 $dp$ 的思想。
倍增算法即在往上走是先走 $2^k$ 步，再走常数步到达最近公共祖先，这样可以加快其速度，并优化暴力算法。
对于求出深度，我们可以使用 dfs：
1
2
3
4
5
| 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$ 步到达的点，则有
我们可以从大到小枚举 $k$，第一个相同的深度再跳到下一层即为最近公共祖先
1
2
| 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模板题完整的代码：
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
| #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;
}
|
后记
这里也可以结合 Tarjan 求 LCA，离线LCA(Tarjan)算法详解。