算法描述
恐龙，是指三角龙、现代鸟类和梁龙的最近共同祖先 (LCA) 及其所有后代。 ——百度百科
假设有一棵树，上面有两个节点，求两个节点最近的共同祖先节点。也可以理解为包含这两个节点的子树是从什么时候分开的。
算法思路
一生二，二生四，四生万物。 ——泥土笨笨
采用倍增的思想，将查询最近共同祖先问题分成若干部：
预处理
预处理一个数组 anc[i][j] 表示 节点的 号祖先的编号。其中有 anc[i][j] = anc[anc[i][j - 1]][j - 1]; 意思是 的 祖先就是 的 的祖先的 祖先。通过这个式子就可以转移了。
转移过程中同时预处理 数组表示深度，后面会用到。
1
2
3
4
5
6
7
8
9
10
11
12
| void dfs(ll u, ll father){
dep[u] = dep[father] + 1;
anc[u][0] = father;
for(ll i = 1; (1 << i) <= dep[u]; i ++){
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
for(ll i = head[u]; i; i = pool[i].next){
if(pool[i].v != father){
dfs(pool[i].v, u);
}
}
}
|
调整深度
追平深度。顾名思义，通过不断调整深度让需要查询的两个节点深度相等。
1
2
3
4
5
6
| if(dep[x] < dep[y]){
swap(x, y);
}
while(dep[x] > dep[y]){
x = anc[x][lg[dep[x] - dep[y]] - 1];
}
|
跳跃结算
一起往上调，跳的步数从 步开始不断尝试，如果调完了发现重合，就放弃，然后尝试少跳一点，以此类推。直到最后到达了最接近共同祖先的位置，即共同祖先的孩子节点。为什么重合要放弃？因为谁也没办法保证当前的重合点是最近的，要不断尝试下调就太麻烦了。
1
2
3
4
5
6
7
8
| if(x == y)return x;
for(ll i = lg[dep[x]]; i >= 0; i --){
if(anc[x][i] != anc[y][i]){
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
|
总代码
例题：洛谷 P3379 【模板】 最近公共祖先（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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const ll MAXN = 500005;
struct Node{
ll v, next;
}pool[2 * MAXN];
ll anc[MAXN][25], dep[MAXN], head[MAXN], nn, lg[MAXN];
ll n, m, s;
void addEdge(ll u, ll v){
pool[++nn].v = v;
pool[nn].next = head[u];
head[u] = nn;
}
void dfs(ll u, ll father){
dep[u] = dep[father] + 1;
anc[u][0] = father;
for(ll i = 1; (1 << i) <= dep[u]; i ++){
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
for(ll i = head[u]; i; i = pool[i].next){
if(pool[i].v != father){
dfs(pool[i].v, u);
}
}
}
ll lca(ll x, ll y){
if(dep[x] < dep[y]){
swap(x, y);
}
while(dep[x] > dep[y]){
x = anc[x][lg[dep[x] - dep[y]] - 1];
}
if(x == y)return x;
for(ll i = lg[dep[x]]; i >= 0; i --){
if(anc[x][i] != anc[y][i]){
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}
int main(){
cin >> n >> m >> s;
for(ll i = 1; i <= n - 1; i ++){
ll x, y;
cin >> x >> y;
addEdge(x, y);
addEdge(y, x);
}
for(ll i = 1; i <= n; i ++){
lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
}
dfs(s, 0);
for(ll i = 1; i <= m; i ++){
ll x, y;
cin >> x >> y;
cout << lca(x, y) << "\n";
}
return 0;
}
|
