这段时间一直在学习LCA的各种算法,下面就对LCA的各种算法进行一次总结:

问题概述

LCA(最近公共祖先)指的是在一棵树上两个节点的最近的公共祖先(这句话好像跟没说差不多),也就是深度最深的公共祖先。 LCA的适用范围非常广,在许多较难的与树有关的题中都会需要用到。 因此,掌握求LCA的方法是非常重要的。

在线算法

树链剖分

上一篇博客中,我已经将树链剖分进行了详细解释。 事实上,在用树链剖分求LCA时,只需要做两遍dfs即可,这样一来,编程复杂度就大大降低了。 预处理的方法和上一篇博客的方法是完全一样的。 在询问LCA时,我们只需要沿着轻/重链向上跳,直到两节点的top相等,最后返回深度较小的节点即可

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
68
69
#include<bits/stdc++.h>
#define begin Begin
#define next Next
#define size Size
#define deep dep
using namespace std;
const int maxn=500000+100;
int begin[maxn],next[maxn*2],to[maxn*2];
int deep[maxn],son[maxn];
int size[maxn],top[maxn],fa[maxn];
int n,m,s,e;
inline void add(int x,int y){
to[++e]=y;
next[e]=begin[x];
begin[x]=e;
}
inline void dfs1(int x){
size[x]=1;
for(int i=begin[x];i;i=next[i]){
int y=to[i];
if(fa[x]==y)continue;
fa[y]=x;
deep[y]=deep[x]+1;
dfs1(y);
if(size[y]>=size[son[x]])son[x]=y;
size[x]+=size[y];
}
}
inline void dfs2(int x,int now){
top[x]=now;
if(son[x])dfs2(son[x],now);
for(int i=begin[x];i;i=next[i]){
int y=to[i];
if(fa[x]==y || son[x]==y)continue;
dfs2(y,y);
}
}
inline int LCA(int x,int y){
int t1=top[x],t2=top[y];
while(t1!=t2){
if(deep[t1]<deep[t2])swap(t1,t2),swap(x,y);
x=fa[t1];
t1=top[x];
}
if(deep[x]>deep[y])swap(x,y);
return x;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
deep[s]=1;
dfs1(s);
dfs2(s,s);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",LCA(x,y));
}
return 0;
}

时间复杂度:O(N+MlogN)O(N+M\log N)(在树的形态为链时最快,为完全二叉树时最慢)

倍增

首先,我们先dfs预处理出每个节点向上跳2i2^i次所到达的节点。

询问时,先根据两个节点的的深度,将深度大的节点向上跳,使得两个节点在同一层上, 如果正好是祖先就结束,否则将两个节点同时向上跳,直到他们父亲相同为止,此时他们的父亲即为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
#include<bits/stdc++.h>
#define begin Bgein
#define next Mext
using namespace std;
const int maxn=500000+10;
int n,m,s;
int begin[maxn*2],next[2*maxn],to[maxn*2],e;
int anc[maxn][30],deep[maxn],fa[maxn];
inline void add(int x,int y){
to[++e]=y;
next[e]=begin[x];
begin[x]=e;
}
inline void dfs(int x){
for(int i=1;i<=22;i++)anc[x][i]=anc[anc[x][i-1]][i-1];
for(int i=begin[x];i;i=next[i]){
int y=to[i];
if(anc[x][0]==y)continue;
anc[y][0]=x;
deep[y]=deep[x]+1;
dfs(y);
}
}
inline int LCA(int x,int y){
if(deep[x]<deep[y])swap(x,y);
for(int i=22;i>=0;i--)
if(deep[anc[x][i]]>=deep[y])x=anc[x][i];
if(x==y)return x;
for(int i=22;i>=0;i--)
if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("LCA.in","r",stdin);
freopen("LCA.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
deep[s]=1;
dfs(s);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",LCA(a,b));
}
return 0;
}

时间复杂度O(NlogN+MlogN)O(N\log N + M \log N)(在树的形态为链时最慢,随机生成的数较快)

ST表

这种算法事实上就是把LCA转化为RMQ,在dfs序中查找区间最小值。

但是这种方法我还没写过,所以先不放代码了

时间复杂度O(NlogN+M+N)O(N\log N + M + N) (在树的形态为完全二叉树时最快)

离线算法

tarjan

tarjan算法其实是dfs+并查集。

我们将给定的树和询问操作分别建图,然后进行dfs。

每搜索到一个点u时,先遍历它的所有子节点v,

如果v还有子节点,则继续便利下去,否则将v并到u上,

然后寻找所有与u有询问关系的点x,

若x已经被访问过,则LCA(u,x)=fa[x] 大致的思路就是这样,具体见代码

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
68
#include<bits/stdc++.h>
#define begin Begin
#define next Next
using namespace std;
const int maxn=500000+100;
int e1,e2;
int begin[maxn],next[maxn*2],to[maxn*2];
int qbegin[maxn],qnext[maxn*2],qto[maxn*2];
int num[maxn*2];
inline void add(int x,int y){
to[++e1]=y;
next[e1]=begin[x];
begin[x]=e1;
}
inline void add1(int x,int y,int z){
qto[++e2]=y;
qnext[e2]=qbegin[x];
qbegin[x]=e2;
num[e2]=z;
}
int n,m,s;
int p[maxn],ans[maxn],f[maxn];
inline int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
inline void link(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return ;
f[fy]=fx;
}
inline void dfs(int x){
p[x]=1;
for(int i=begin[x];i;i=next[i]){
int y=to[i];
if(p[y])continue;
dfs(y);
link(x,y);
}
for(int i=qbegin[x];i;i=qnext[i]){
int y=qto[i];
if(!p[y])continue;
ans[num[i]]=find(y);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add1(x,y,i);
add1(y,x,i);
}
dfs(s);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
puts("");
return 0;
}

时间复杂度O(N+M)O(N+M)

总结

求LCA的方法大致就是这些。 对于不同的题目,我们还是要根据数据范围来选择合适的算法求解。 当然,当数据范围不是很大时,选择自己最熟悉的写就可以了。 就像文章开头所说,这些求LCA的算法是非常实用的。