倍增算法求最近公共祖先
一、概述
在图论和计算机科学中，最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。 --*
上图中，
L
C
A
(
11
,
8
)
=
8
LCA(11, 8)=8
LCA(11,8)=8，
L
C
A
(
11
,
9
)
=
1
LCA(11, 9)=1
LCA(11,9)=1，
L
C
A
(
7
,
8
)
=
2
LCA(7, 8)=2
LCA(7,8)=2。求
L
C
A
LCA
LCA有很多算法，比如倍增算法，Tarjan(离线)算法， 与RMQ问题的转换等。
二、朴素算法
求
L
C
A
(
v
,
w
)
LCA(v, w)
LCA(v,w)比较直观想法是，先将
v
v
v，
w
w
w中层次较深者提升到同一深度，然后一起一步一步向上爬， 直到相遇，相遇节点则为
L
C
A
(
v
,
w
)
LCA(v, w)
LCA(v,w)。
如下图， 求
L
C
A
(
11
,
9
)
LCA(11, 9)
LCA(11,9)时，先将较深节点
11
11
11提升到其祖先节点
8
8
8，此时， 求
L
C
A
(
11
,
9
)
LCA(11, 9)
LCA(11,9)相当于求
L
C
A
(
8
,
9
)
LCA(8, 9)
LCA(8,9)，然后节点
8
8
8和
9
9
9再沿着其祖先链一步一步向上爬。整个过程为，
L
C
A
(
11
,
9
)
LCA(11, 9)
LCA(11,9)=
L
C
A
(
8
,
9
)
LCA(8, 9)
LCA(8,9)=
L
C
A
(
5
,
6
)
LCA(5, 6)
LCA(5,6)=
L
C
A
(
2
,
3
)
LCA(2, 3)
LCA(2,3)=
1
1
1。
需要注意，如果
v
v
v，
w
w
w之间存在祖先关系，比如求
L
C
A
(
8
,
11
)
LCA(8, 11)
LCA(8,11)，节点
11
11
11提升到节点
8
8
8时就已经相遇了，就不需要后面步骤了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
// 最多节点数
const int maxn = 500005;
// n ： 节点数
// s ： 根节点编号
// fa[i] ： 节点i父节点编号
// depth[i] ：节点i深度
int n, s, head[maxn], fa[maxn], depth[maxn], m, v, w, cnt;
struct E{
int to, next;
} edge[2*maxn];
// 链式向前星存树模板代码
void add_edge(int from, int to){
edge[cnt].to = to;
edge[cnt].next = head[from];
head[from] = cnt++;
}
// 深度优先搜索, 预处理每个节点深度和父节点编号
// r ： 当前根节点编号
// p ： r节点父节点编号
void dfs(int r, int p){
// 当前节点深度为父节点深度+1
depth[r] = depth[p]+1;
fa[r] = p;
// 递归到子树
for(int i = head[r]; i != -1; i = edge[i].next){
int to = edge[i].to;
if(to != p){
dfs(to, r);
}
}
}
int main(){
memset(head, -1, sizeof(head));
cin>>n>>s;
for(int i = 0; i < n-1; i++){
cin>>v>>w;
add_edge(v, w);
add_edge(w, v);
}
dfs(s, -1);
cin>>v>>w;
// 确保depth[v] >= depth[w]， 即节点v是深度较深节点
if(depth[v] < depth[w]) swap(v, w);
// 节点v一步一步向上爬到和节点w同深度
while(depth[v] > depth[w]) v = fa[v];
// 节点v和节点w一步一步沿着父节点向上爬, 直到相遇
// 如果节点v和节点w之间具有祖先关系, 则通过上一个while循环后这里v等于w，不会进入这个循环
while(v != w){
v = fa[v];
w = fa[w];
}
cout<<v<<endl;
}
神马，这就完了吗？ 说好的倍增呢？
前文已经说了，这只是一个直观想法，其实这个算法可以进行优化的。
这个算法中有两个向上一步一步爬的地方：
- 节点 v v v沿着父节点一步一步向上爬到和节点 w w w同深度；
- 节点 v v v和节点 w w w沿着各自的父节点一步一步向上爬直到他们相遇；
这样一步一步向上爬是不是感觉很费经？有没有更高效的算法呢？
三、用倍增优化
接下来就是我们主角倍增上场了。
1. 倍增思想
我们知道任何一个正整数都可以用
2
2
2 的幂次方之和表示，相当于将这个数转化成
2
2
2进制。那么在向上爬的过程中可不可以一次爬
2
2
2 的幂次方步长，即一次爬
2
0
2^0
20，
2
1
2^1
21，
2
2
2^2
22，
2
3
2^3
23，
2
4
2^4
24 …
2
30
2^{30}
230这些步长，这样最多向上爬
30
30
30次左右。比如
7
=
2
2
+
2
1
+
2
0
7=2^2+2^1+2^0
7=22+21+20，我们只需要爬三步，这三步步长分别为
1
1
1，
2
2
2，
4
4
4，这样效率呈幂次方提升，这就是倍增；
但是，这里还有一个关键问题，不知道总共需要爬多少步，那怎么用
2
2
2 的幂次方之和表示，总不能每个
2
2
2 的幂次方都爬吧。
比如总共需要爬
5
5
5步，
2
0
+
2
1
+
2
2
+
2
3
=
1
+
2
+
4
=
7
>
5
2^0+2^1+2^2+2^3=1+2+4=7>5
20+21+22+23=1+2+4=7>5，已经爬过了，还得回溯。
2. 实现
虽然不知道总共需要爬多少步，但是知道一个步长能不能爬。
- 对于第一种情况，在节点
v
v
v向上爬到和节点
w
w
w同深度过程中，如果爬了这一步发现其深度小于
w
w
w深度，则这一步不能爬；
例如上面这棵树， v = 11 v=11 v=11， w = 2 w=2 w=2时， d e p t h [ v ] = 6 depth[v]=6 depth[v]=6， d e p t h [ 2 ] = 6 depth[2]=6 depth[2]=6，对于一步长度为 2 4 = 16 2^4=16 24=16时，如果爬了这步， d e p t h [ v ] = 6 − 16 = − 10 < 2 depth[v]=6-16=-10<2 depth[v]=6−16=−10<2，所以这步不能爬， 但是，如果步长为 2 2 = 4 2^2=4 22=4时，如果爬了这步， d e p t h [ v ] = 6 − 4 = − 10 = 2 depth[v]=6-4=-10=2 depth[v]=6−4=−10=2，这一步可以爬。 - 对于第二种情况，节点 v v v和节点 w w w沿着各自的祖先节点向上爬时，如果爬了这一步还没有到达公共祖先则能爬，否则这一步不能爬。我们的策略是要把公共祖先之前的所有步爬完，最后都停留在公共祖先前一步，那再爬一步 2 0 = 1 2^0=1 20=1就到达最近公共祖先。
例如上面这棵树，
v
=
4
v=4
v=4，
w
=
5
w=5
w=5时，对于步长
2
1
=
2
2^1=2
21=2，如果爬了这一步则
v
=
1
v=1
v=1，
w
=
1
w=1
w=1，爬到公共祖先上，这一步不能爬。但是对于步长
2
0
=
1
2^0=1
20=1，爬了这一步后
v
=
2
v=2
v=2，
w
=
2
w=2
w=2，相遇了，也不能爬这一步。
知道了一个步长能不能爬有什么好处呢？
我们联想我们平时怎么把一个十进制数转换成二进制的， 当然我们可以使用除二取余倒排数这种方法来做，我们还可以试减这种方法，例如对于
11
11
11，我们可以从一个最接近
11
11
11但小于等于
11
11
11的一个
2
2
2 的幂次方的数开始向下试减，不断重复，使其最终减为零；比如
11
11
11可以减掉
2
3
=
8
2^3=8
23=8，不能减掉比
2
3
2^3
23更大的
2
2
2的幂次方，所以
11
=
2
3
+
5
11=2^3+5
11=23+5，
5
5
5可以减掉
2
2
=
4
2^2=4
22=4，所以
11
=
2
3
+
2
2
+
1
11=2^3+2^2+1
11=23+22+1，
1
1
1只能减掉
2
0
=
1
2^0=1
20=1，所以
11
=
2
3
+
2
2
+
2
0
11=2^3+2^2+2^0
11=23+22+20。
这里能不能减掉一个
2
2
2 的幂次方，是不是就是上面的一个步长为
2
2
2 的幂次方步能不能走，可以借鉴这种思想。
对于第一种情况，我们是知道
v
v
v是要向上走
d
e
p
t
h
[
w
]
−
d
e
p
t
h
[
v
]
depth[w]-depth[v]
depth[w]−depth[v]步的，所以我们可以从步长最接近
d
e
p
t
h
[
w
]
−
d
e
p
t
h
[
v
]
depth[w]-depth[v]
depth[w]−depth[v]但小于等于
d
e
p
t
h
[
w
]
−
d
e
p
t
h
[
v
]
depth[w]-depth[v]
depth[w]−depth[v]
2
2
2 的幂次方即
2
2
2 的
⌊
l
o
g
2
d
e
p
t
h
[
w
]
−
d
e
p
t
h
[
v
]
⌋
\lfloor log _{2}^{depth[w]-depth[v]} \rfloor
⌊log2depth[w]−depth[v]⌋次方步开始向下试走，最终必定走到和
w
w
w同深度。
例如上图是一个特殊例子，
v
=
10
v=10
v=10和
w
=
1
w=1
w=1具有祖先关系，
d
e
p
t
h
[
w
]
−
d
e
p
t
h
[
v
]
=
9
depth[w]-depth[v]=9
depth[w]−depth[v]=9，
⌊
l
o
g
2
9
⌋
=
3
\lfloor log _{2}^{9} \rfloor=3
⌊log29⌋=3，所以从步长为
2
3
=
8
2^3=8
23=8开始试走，先走一步
2
3
2^3
23到达节点
2
2
2，此时
d
e
p
t
h
[
w
]
−
d
e
p
t
h
[
v
]
=
1
depth[w]-depth[v]=1
depth[w]−depth[v]=1，
2
2
=
4
>
1
2^2=4 >1
22=4>1 不能走，
2
1
=
2
>
1
2^1=2 >1
21=2>1 不能走，
2
0
=
1
=
1
2^0=1 =1
20=1=1 走完这步后和节点
w
w
w同深度。
对于第二种情况，节点
v
v
v和节点
w
w
w沿着各自的祖先节点向上爬，我们并不知道需要向上爬多少步，但步数肯定小于
d
e
p
t
h
[
v
]
depth[v]
depth[v]或者
d
e
p
t
h
[
w
]
depth[w]
depth[w]，所以我们可以从步长为
2
2
2的
⌊
l
o
g
2
d
e
p
t
h
[
v
]
−
1
⌋
\lfloor log _{2}^{depth[v]-1} \rfloor
⌊log2depth[v]−1⌋的步开始试走；
例如上图，
v
=
18
v=18
v=18和
w
=
19
w=19
w=19，
d
e
p
t
h
[
18
]
=
d
e
p
t
h
[
19
]
=
11
depth[18]=depth[19]=11
depth[18]=depth[19]=11，
⌊
l
o
g
2
11
−
1
⌋
=
3
\lfloor log _{2}^{11-1} \rfloor=3
⌊log211−1⌋=3，但
v
v
v和
w
w
w如果沿着各自祖先链向上爬步长为
2
3
=
8
2^3=8
23=8一步后，在节点
3
3
3相遇了，所以
2
3
=
8
2^3=8
23=8这一步不能爬；
v
v
v和
w
w
w向上爬步长为
2
2
=
4
2^2=4
22=4一步后，
v
=
10
v=10
v=10和
w
=
11
w=11
w=11，未相遇，这一步可以走；然后判断步长为
2
1
=
2
2^1=2
21=2这步能不能爬，爬了这一步后
v
=
6
v=6
v=6和
w
=
7
w=7
w=7，未相遇，这一步可以走；最后判断步长为
2
0
=
1
2^0=1
20=1这步能不能爬，爬了这一步后
v
=
4
v=4
v=4和
w
=
5
w=5
w=5，未相遇，这一步可以走；最终，
v
v
v和
w
w
w都到公共祖先链的下一个节点，在向上走步长为
1
1
1的一步后到达最近公共祖先节点。
3. 算法核心
要实现该算法，这里有出现了两个难题：
- 对于节点 v v v，距离为 2 2 2的幂次方的祖先节点编号怎么求，从节点 v v v出发，沿着祖先链走一步步长为 2 2 2的幂次方的步就到达了该节点，这可以说是倍增核心；
- 对于任意距离 d d d， ⌊ l o g 2 d ⌋ \lfloor log _{2}^{d} \rfloor ⌊log2d⌋怎么求；
对于第一个问题，我们之前是使用 f a [ i ] fa[i] fa[i]数组记录节点 i i i父节点的，并在从父节点递归到子节点时记录子节点的 f a [ ] fa[] fa[]，类似于递推。但是现在不仅要记录节点 i i i的父节点，还要记录与其距离为 2 1 2^1 21， 2 2 2^2 22， 2 3 2^3 23， 2 4 2^4 24 … 的祖先节点，所以将 f a [ ] fa[] fa[]定义成以为数组肯定不够用，需要将其定义为二维数组 f a [ i ] [ j ] fa[i][j] fa[i][j]，表示与节点 i i i相聚 2 j 2^j 2j的祖先节点编号， f a [ i ] [ 0 ] fa[i][0] fa[i][0]和原来 f a [ i ] fa[i] fa[i]相同，存储节点 i i i直接父节点。那 f a [ i ] [ j ] fa[i][j] fa[i][j]怎么求呢？
如上图，对于节点 10 10 10， d e p t h [ 10 ] = 10 depth[10]=10 depth[10]=10， ⌊ l o g 2 10 − 1 ⌋ = 3 \lfloor log _{2}^{10-1} \rfloor=3 ⌊log210−1⌋=3，只需要求 f a [ 10 ] [ 0 ] fa[10][0] fa[10][0]， f a [ 10 ] [ 1 ] fa[10][1] fa[10][1]， f a [ 10 ] [ 2 ] fa[10][2] fa[10][2]， f a [ 10 ] [ 3 ] fa[10][3] fa[10][3]。例如， f a [ 10 ] [ 3 ] = f a [ 6 ] [ 2 ] = 2 fa[10][3]=fa[6][2]=2 fa[10][3]=fa[6][2]=2，看出什么端倪出来没？大概什么意思呢， 2 j = 2 j − 1 + 2 j − 1 2^j=2^{j-1}+2^{j-1} 2j=2j−1+2j−1，就是说如果要从节点 i i i跳到距离为 2 j 2^j 2j的祖先节点，可以先跳到距离为 2 j − 1 2^{j-1} 2j−1次方的中间节点节点，再从这个节点出发跳一步 2 j − 1 2^{j-1} 2j−1就到了距离 i i i为 2 j 2^j 2j的祖先节点。与节点 i i i距离为 2 j − 1 2^{j-1} 2j−1次方的中间节点节点是不是就是 f a [ i ] [ j − 1 ] fa[i][j-1] fa[i][j−1]，在从这个几点出发跳一步 2 j − 1 2^{j-1} 2j−1是不是就是 f a [ f a [ i ] [ j − 1 ] ] [ j − 1 ] fa[fa[i][j-1]][j-1] fa[fa[i][j−1]][j−1]，所以 f a [ i ] [ j ] fa[i][j] fa[i][j]可以通过 f a [ f a [ i ] [ j − 1 ] ] [ j − 1 ] fa[fa[i][j-1]][j-1] fa[fa[i][j−1]][j−1]递推。
对于第二个问题，我们可以用递推。假设数组
l
g
[
i
]
lg[i]
lg[i]存值为
⌊
l
o
g
2
i
⌋
\lfloor log _{2}^{i} \rfloor
⌊log2i⌋，那么在知道
l
g
[
i
−
1
]
lg[i-1]
lg[i−1]情况下如何推出
l
g
[
i
]
lg[i]
lg[i]？
对于
i
i
i如果可以刚好表示成
2
2
2的幂次方，那么
i
−
1
i-1
i−1就不能表示成
2
2
2的幂次方，
l
g
[
i
]
lg[i]
lg[i]需要将
l
g
[
i
−
1
]
lg[i-1]
lg[i−1]向下取整部分收为
1
1
1，即
l
g
[
i
]
=
l
g
[
i
+
1
]
+
1
lg[i]=lg[i+1]+1
lg[i]=lg[i+1]+1；如果
i
i
i不能表示成
2
2
2的幂次方，则直接
l
g
[
i
]
=
l
g
[
i
+
1
]
lg[i]=lg[i+1]
lg[i]=lg[i+1]。但是
i
i
i是不是
2
2
2的幂次方也不好确认，我们可以这样，让lg[i]存
⌊
l
o
g
2
i
⌋
+
1
\lfloor log _{2}^{i} \rfloor+1
⌊log2i⌋+1，在推
l
g
[
i
]
lg[i]
lg[i]时，我们看下
2
l
g
[
i
−
1
]
2^{lg[i-1]}
2lg[i−1]是不是等于
i
i
i，如果相等说明进入刚好遇到
2
2
2的幂次方，需要
+
1
+1
+1，
2
2
2的幂次方可以通过位右移可以很快算出来。
代码如下：
for(int i = 1; i <= n; ++i){
lg[i] = lg[i-1] + (1 << lg[i-1] == i);
}
for(int i = 1; i <= n; ++i) lg[i]--;
OK， 所有问题搞定，直接上代码：
#include<bits/stdc++.h>
using namespace std;
// 最多节点数
const int maxn = 500005;
// fa[i][j] : 与节点i相距2的j次方的祖先节点编码
// depth[i] : 节点i深度
// lg[i] : lg2(i) 向下取整
// n : 节点数
// s : 根节点编号
int head[maxn], fa[maxn][32], depth[maxn],lg[maxn], cnt=0, n, s;
// 链式向前星存树模板代码
struct E {
int to, next;
} edge[maxn << 1];
void add(int from, int to) {
edge[cnt].to = to;
edge[cnt].next = head[from];
head[from] = cnt++;
}
void dfs(int r, int p) {
depth[r] = depth[p] + 1;
// 直接父节点，
fa[r][0] = p;
// 递推，把与节点i相距2的1次方到2lg[depth[r]]祖先节点编码全部推出
for(int i = 1; i <= lg[depth[r]-1]; ++i)
// 倍增核心代码
fa[r][i] = fa[fa[r][i-1]][i-1];
// 递归到子树
for(int i = head[r]; i != -1; i = edge[i].next)
if(edge[i].to != p)
dfs(edge[i].to, r);
}
int LCA(int u, int w) {
if(depth[u] < depth[w]) swap(u, w);
// 倍增让u跳到和w同深度
while(depth[u] > depth[w])
u = fa[u][lg[depth[u]-depth[w]]];
if(u == w) return w;
// 倍增让u和w LCA前的距离跳2完
for(int k = lg[depth[u]]; k >= 0; --k)
if(fa[u][k] != fa[w][k])
u = fa[u][k], w = fa[w][k];
// 再跳一步到LCA
return fa[u][0];
}
int main() {
memset(head, -1, sizeof(head));
cin>>n>>s;
int x, y;
for(int i = 1; i <= n-1; ++i) {
cin>>x>>y;
add(x, y);
add(y, x);
}
for(int i = 1; i <= n; ++i)
lg[i] = lg[i-1] + (1 << lg[i-1] == i);
for(int i = 1; i <= n; ++i) lg[i]--;
dfs(s, 0);
cin>>x>>y;
cout<<LCA(x, y)<<endl;
return 0;
}
4. 时间复杂度分析
函数dfs(int r, int p)需要递归到每个节点时间复杂度为
O
(
n
)
O(n)
O(n)，对每个节点需要求与其相距
2
2
2的幂次方祖先节点编号时间复杂度
O
(
l
g
n
)
O(lgn)
O(lgn)，所以这个函数总时间复杂度
O
(
n
l
g
n
)
O(nlgn)
O(nlgn)。LCA(int u, int w)函数时间复杂度为
O
(
l
g
n
)
O(lgn)
O(lgn)，所以总时间复杂度为
O
(
n
l
g
n
)
O(nlgn)
O(nlgn)；