最近公共祖先 LCA(Least Common Ancestors)

倍增算法求最近公共祖先

一、概述

在图论和计算机科学中,最近公共祖先(英语:lowest common ancestor)是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里,我们定义一个节点也是其自己的后代,因此如果v是w的后代,那么w就是v和w的最近公共祖先。 --*

最近公共祖先 LCA(Least Common Ancestors)

上图中, 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。
最近公共祖先 LCA(Least Common Ancestors)

需要注意,如果 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同深度。
最近公共祖先 LCA(Least Common Ancestors)
例如上图是一个特殊例子, 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​⌋的步开始试走;
最近公共祖先 LCA(Least Common Ancestors)
例如上图, 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]怎么求呢?

最近公共祖先 LCA(Least Common Ancestors)

如上图,对于节点 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);

上一篇:mysql Access denied; you need (at least one of) the SUPER privilege(s) for this operation


下一篇:my live house soud / audio / Hi-Fi / xiaodu dajingang