【笔记】图论-最近公共祖先

【笔记】图论-最近公共祖先

前置知识:

概念

众所周知,在一棵树上,每个点都有其祖先,而最近公共祖先,顾名思义,就是指一个或几个点共有的祖先,且这个祖先的深度最大,为了方便,我们把一个或几个点的最近公共祖先记为LCA(u1,u2,,un)\text{LCA}(u_1,u_2,\cdots,u_n)

举个例子,这是一棵树:

一棵树

其中,LCA(3,12)=2\text{LCA}(3,12)=2LCA(11,12)=4\text{LCA}(11,12)=4LCA(10,14)=1\text{LCA}(10,14)=1LCA(12,2)=2\text{LCA}(12,2)=2,而LCA(7,8)1\text{LCA}(7,8)\neq 1,因为55也是他们的公共祖先,并且55的深度比11大。

另外,LCA 不一定只是在二叉树上才有(废话),上图很明显就不是一个二叉树

一般来说,LCA 有四种求法,即倍增、Tarjan、RMQ+ST 表和树链剖分,但本文只记录了三种,没有关于树链剖分的介绍,主要是因为树剖码量比较大,而且如果只是单纯地求某两点的 LCA 的话很浪费,这玩意用途很大,后面会专门写一篇文章来介绍,到时候反正也要说,所以这里就先不管了

倍增

倍增算是比较常见的求 LCA 的方法了,同时也是我个人比较喜欢用的一种方法。倍增是在线算法,相当于就是不管什么时候,只要你想求 LCA,就可以跑一遍倍增,不需要事先知道所有的输入数据,也就是常说的输入一个回答一个,与之相反的是离线算法,这在 Tarjan 里面会更详细地讲

思路

一般来说,当我们还没有学过 LCA 的算法之前,我们首先想到的是暴力,先把两个点挪到相同的高度,然后把它们一层一层往上挪,它们相遇的时候所在的点就是它们的最近公共祖先,但是很明显,这样子太慢了,首先是需要用 DFS 预处理出每个节点的父亲及其深度,时间复杂度为O(n)O(n),然后每次查询的时间复杂度大约为O(logn)O(\log n)(特殊情况另当别论)

而倍增相当于是对暴力算法的优化,不再是一层一层地挪,而是用一个fa[u][i]数组来表示uu的第2i2^i个祖先,实现快速移动

要想理解这一点,首先要理解一点,即通过上述方法,可以使树上的一个点移动到任意一个祖先节点

假设这个点的深度为depudep_u,它的祖先节点的深度为depvdep_v,那么要跳到vv去,之间会经过depudepv+1dep_u-dep_v+1个点,我们把这个数转化成二进制(假设为55),则有:

(5)10=(101)2=20+22(5)_{10}=(101)_2=2^0+2^2

也就是说,uu只需要先跳到fa[u][0],再跳到fa[u][2](这里的uu已经是原来的fa[u][0]了)就可以到vv

另外这个数组有一个递推公式,思路也比较简单,就是自己的第2i12^{i-1}个父亲的第2i12^{i-1}个父亲就是自己的第2i2^i个父亲,即fa[u][i]=fa[fa[u][i-1]][i-1]

既然如此,倍增算法的思路也就出来了,在一开始用 DFS 预处理出所有的fa[u][i],然后每次查询时先把两点调到相同的高度,再让两点一起移动就可以了,而这两个过程都可以采用上述方法

但这样又会有一个小问题,我并不知道LCA(u,v)\text{LCA}(u,v)的深度,没有办法预先知道要跳多少,所以在这个过程中就有可能跳到 LCA 的上方,这个问题也好解决,既然我不知道哪个祖先是它们的最近公共祖先,那我就干脆不跳到他们的公共祖先,只是跳到最接近它们公共祖先的地方,即它们 LCA 的下一层,然后最后返回fa[u][0]就可以了,这样判断起来也很容易,如果是跳到了共同的祖先,那么fa[u][i]一定会等于fa[v][i],所以在每次循环时判断一下就好了

还有一点,在最后这里uuvv一起跳的时候,这个循环的顺序和移动uuvv的深度时的顺序是相反的,也就是说这里要把ii从大往小循环,可以这样理解,这个跳的过程就是为这个深度差的二进制位填11的过程,每填一个11,就跳到对应的fa[u][i]ii为这个11在二进制数里面的位数),之前我们知道这个值是多少,所以可以从低位开始一位一位按照这个给定的值去填,但此时我们并不知道这个值是多少,所以我们必须要尝试,如果从低位开始,那么有可能这一位本来是为00的,但填了11之后并没有超过原数的大小,只有到后面我们才会发现填错了,而如果从高位开始,那么就不会有这种问题。可以联系一下我们小学时学的比较数的大小的方法,先把最低位对齐,然后从最高位一位一位开始比,如果在某一位上一个数的数字小于另一个,那么就可以判断这个数一定小于那个数,这里也是一样的,如果本来是00,被填成了11,那么马上就可以发现这个数大于了深度差,也就是跳到了公共祖先上去

大概的思路就是这样了,可能写的有点迷,要是搞不懂的可以在评论里说一声,我好改进一下

过程模拟

众所周知,手动模拟能解决一切疑惑

我们用上面那棵树来模拟一下这个过程,假设我们求的是LCA(13,12)\text{LCA}(13,12)

  1. 发现1212的深度和1313不一样,并且比它深,所以要将其上移,此时深度的差值为11,因此只需要一次u=fa[u][0]即可解决问题,此时1212变为44,而44不为1313,所以1313并不是LCA(13,12)\text{LCA}(13,12)
  2. 然后是上跳,从nn(点数)的二进制最高位开始试(这里求nn的二进制最高位的位数ii就是求logn\log n,有一个简便方法:i=log(n)/log(2)+0.5,这个0.50.5是起四舍五入的作用的),首先是fa[4][4]fa[13][4],发现它们都等于00,则不管它,继续。然后是fa[4][3]fa[13][3],和上面一样,不管,继续。fa[4][2]fa[13][2]也是都等于00,直到fa[4][1]fa[13][1]才都等于11,虽然我们知道这就是它们的 LCA,但程序并不能分辨这是不是最近的公共祖先,所以还是跳过,最后fa[4][0]=2fa[13][0]=6,这下才能执行u=fa[u][i],v=fa[v][i]的程序,两个点分别变为2266
  3. 最后,返回fa[2][0]=1,求出LCA(13,12)=1\text{LCA}(13,12)=1,完毕

参考代码

题目:洛谷 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
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
int next;
int to;
};
Edge edge[1000001];//记得要建双向边,因为在输入的时候并不知道谁是谁的父亲
int n,m,s,cnt,head[500001];
int log2n,dep[500001],fa[500001][21];
//log2n 上面提到过,记录的是 log(n),dep 数组记录每个点的深度,fa[u][i] 记录第 u 个点的第 2^i 个父亲
void add_edge(int u,int v)
{
cnt++;
edge[cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
}
void dfs(int u,int father)//预处理求出 dep 和 fa 数组
{
fa[u][0]=father;
dep[u]=dep[father]+1;
for(int i=1;(1<<i)<=dep[u];i++)//1<<i 相当于 2^i,这里要保证 2^i 小于 u 的深度
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=edge[i].next)
if(edge[i].to!=father)
dfs(edge[i].to,u);
}
int lca(int u,int v)//倍增求 LCA
//因为 u 和 v 的值会在函数里发生改变,所以一定要用传参函数,也就是我们平时习惯的那样
{
int depu=dep[u],depv=dep[v];
//这里也不能少,和上面一样,u 和 v 的值会在函数里发生改变,但深度又要保持不变,所以另外用两个变量来代替
if(depu!=depv)//如果两个点深度不一样,所以需要调到相同高度
{
if(depu<depv)//因为默认是移动 u 点,所以要保证 u 在 v 的下方
{
swap(u,v);
swap(depu,depv);
}
for(int i=0;i<=depu-depv;i++)
//准确来说这里应该是 log(depu-depv)/log(2)+0.5,但我嫌麻烦,而且这样也是对的
if((1<<i)&(depu-depv))//判断第 (depu-depv) 的第 i 位是否为 1,可以自己算一下
u=fa[u][i];
}
if(u==v)//不要忘了判断,如果这里漏了,那么最后的返回值就是 fa[LCA(u,v)][0]
return u;
for(int i=log2n;i>=0;i--)//从高位向低位填 1
if(fa[u][i]!=fa[v][i])//判断这一次所跳的点是否为公共祖先
{
u=fa[u][i];
v=fa[v][i];
}
return fa[u][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
log2n=log(n)/log(2)+0.5;
dfs(s,0);
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)O(n\log n)预处理,O(logn)O(\log n)查询,同时这个nn一般来说最大也就是1e51e5左右,而logn\log n则不会超过2020,所以总体来说是很优秀的

Tarjan

这个 Tarjan 并不是求强连通分量的那个 Tarjan,只是因为是同一个人发明的,所以都叫一样的名字(误导了我整整一学期、=_=),关于这一点有兴趣的同志可以看一下这篇文章:Tarjan 大佬的算法们(根据这篇文章和百度百科看来,Tarjan 这个巨佬至少发明了三四种算法和数据结构。)

Tarjan 是一种离线算法,也就是说和上面的倍增不同,它需要事先知道我们有哪些问题,然后一次性全部解决掉,好处是时间复杂度很棒,对于qq次询问,Tarjan 的时间复杂度仅为O(n+q)O(n+q),但坏处也显而易见,不够灵活

思路

Tarjan 其实比较容易理解,先对整棵树进行 DFS,在这个过程中,每到一个点uu并搜完这个点所有的子树后,查看有没有要查询的LCA(u,v)\text{LCA}(u,v)(下称“有询问关系”),如果有,再看一下vv是否遍历完毕,如果是,那么就找vv并查集的祖宗(也就是并查集的根结点,不是指这棵树上vv的祖宗),这个祖宗就是LCA(u,v)\text{LCA}(u,v),最后标记自己已经遍历完毕,并把自己合并到父亲节点上(用并查集)

这时有一个小问题

为什么并查集的祖宗就是 LCA???

因为在这个过程中,我们是先遍历完所有子树才把自己合并到父亲节点上,此时我们分两种情况讨论,如果uuvv互相都不是对方的祖先,那么它们就处在两棵不同的子树上,如果遍历到vv时发现uu已经被遍历过了,那么此时uu的并查集的祖宗一定在uuvv所属的子树分叉的地方,因为这个点的子树还没有遍历完,还差vv这棵,所以自然也就不会合并到自己的父亲上去,而这个分叉的地方很明显就是LCA(u,v)\text{LCA}(u,v)。如果uuvv中某一个点是对方的祖先(假设vvuu的祖先),那就更好办了,当遍历到uu时,vv由于自己的子树还没遍历完,所以不会打标记,而回溯到vv时,uu已经遍历完毕,而vv还没有把自己合并到父亲节点,所以目前uu的所属的并查集的根是vv,也就是LCA(u,v)=v\text{LCA}(u,v)=v

搞清楚了这一点,这个算法也就很简单了,如果还有点搞不清楚,那就来手动模拟一次

过程模拟

老规矩,上图

这次我们多弄一点,要求求出LCA(5,3),LCA(7,8),LCA(2,5),LCA(1,4)\text{LCA}(5,3),\text{LCA}(7,8),\text{LCA}(2,5),\text{LCA}(1,4)

  1. 首先从点11开始,一路向下,一直到点55,发现这是叶子节点,查看与55有询问关系的3322,发现它们都还没有标记,所以不管,标记vis5=1,fa5=2vis_5=1,fa_5=2,然后回溯
  2. 回溯到点22,发现它的子节点都搜完了,而有询问关系的点55已经被打了标记,所以查看它的祖先为22,因此LCA(2,5)=2\text{LCA}(2,5)=2,标记一下vis2=1,fa2=1vis_2=1,fa_2=1,回溯
  3. 又到了点11,由于子树还没有搜完,因此暂时不查看与点11有询问关系的点,也不打标记,先搜一下点33,一直往下到点77
  4. 77也是个叶子节点,但与77有询问关系的88还没有标记,所以也不管,标记vis7=1,fa7=3vis_7=1,fa_7=3,回溯到点33,接着又搜点88
  5. 到了点88,发现有询问关系的点77已经被打了标记,所以查看77的祖宗,为33,所以LCA(7,8)=3\text{LCA}(7,8)=3,再标记vis8=1,fa8=3vis_8=1,fa_8=3,回溯
  6. 回到点33,这时点33的子节点全部搜完,所以查看与点33有询问关系的点55,发现已经被打了标记,所以查看其祖宗,为点11fa5=2,fa2=1fa_5=2,fa_2=1,并查集基本操作),因此LCA(5,3)=1\text{LCA}(5,3)=1,老规矩,打个标记,vis3=1,fa3=1vis_3=1,fa_3=1,回溯
  7. 又回到了点11,还是没有搜完它的儿子,所以还是不管,来到点44
  8. 这点44也是个叶子节点,与11有询问关系,但11还没被打标记,所以还是vis4=1,fa4=1vis_4=1,fa_4=1,回溯
  9. 回到点11,这回终于把它的儿子搜完了,查看点44的祖宗为点11,因此LCA(1,4)=1\text{LCA}(1,4)=1,搜索结束
  10. 至此,所有要求的 LCA 都求出来了,直接输出即可

个人感觉不难懂吧,但顺序一定要整好,先查看有询问关系的点,再标记自己,否则就会出现LCA(2,5)=1\text{LCA}(2,5)=1的事情

参考代码

老实说我个人并不是很喜欢用 Tarjan 算法来求LCA\text{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
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
int next;
int to;
};
struct Que
{
int next;
int to;
int p;//p 表示的是这个询问对应的是第几个问题,方便最后按照顺序输出答案
};
Edge edge[1000001];
Que que[1000001];//我这里使用链式前向星存储询问,这样便于查询某一个点的所有询问,而不用每次都遍历所有问题
//其实是因为当时我太弱了,否则用 vector 来存其实更方便
int n,m,s,cnt,f[500001],head[500001],queh[500001],vis[500001],ans[500001];
int find(int x)//并查集基础操作不解释
{
return f[x]==x?f[x]:f[x]=find(f[x]);
}
void add_edge(int u,int v)
{
cnt++;
edge[cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
}
void add_que(int u,int v,int i)
{
cnt++;
que[cnt].next=queh[u];
que[cnt].to=v;
que[cnt].p=i;
queh[u]=cnt;
}
void lca(int u,int father)
{
for(int i=head[u];i;i=edge[i].next)//首先搜索这个点的所有子树
{
int v=edge[i].to;
if(v!=father&&!vis[v])
{
lca(v,u);
f[find(v)]=find(u);//这里我是回溯到父节点时才打标记,效果和上面说的查看完所有询问再标记是一样的
//另外,其实直接 f[v]=u 就可以了,这里只是打并查集习惯了而已
vis[v]=1;
}
}
for(int i=queh[u];i;i=que[i].next)//查看所有询问,如果对方已经被打了标记,就求出答案
if(vis[que[i].to])
ans[que[i].p]=find(que[i].to);
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
cnt=0;
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add_que(a,b,i);//这里要建双向边,但对应的 p 值应该是一样的
add_que(b,a,i);
}
lca(s,0);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}

整个过程还是很简单,如果还有什么不懂的可以在评论里问反正也不会有人看我博客的

RMQ+ST 表

这也是一种在线算法,时间复杂度很强,预处理O(nlogn)O(n\log n),而询问只需要O(1)O(1),不过有点难想,最重要的就是怎样把求 LCA 转化成 RMQ,以及为什么这样做是对的,搞懂了这一点后,代码其实就好写了

关于 ST 表以及相应的用它来求 RMQ,请自行上网查找,这里不再赘述

思路

在开始之前,我们先引入一个东西,欧拉序列

所谓欧拉序列,其实就是一棵树的 DFS 序,只不过每到一个节点都得记录一下,就连回溯时也是一样

以上面 Tarjan 算法那张图为例

这棵树的欧拉序列是这样的

序号12345678910111213
1252137383141

这个序列的长度为2n12n-1nn为这棵树的点数(其实上面这张图只有77个点,我漏了一个66。),这个看网上都很少有证明的,虽然不是很重要,但我觉得还是应该知道为妙

首先设点uuxux_u个儿子,点的标号从11nn,易得,点uu在这个序列中出现的次数为xu+1x_u+1,因为每个儿子回溯时都会出现一次,同时一开始从父亲下来的时候还会出现一次

容易得出

i=1nxi=n1\sum\limits_{i=1}^n x_i=n-1

因为每个点会且只会被算一次(因为每个点只有一个父亲嘛),同时点11作为根节点,没有父亲,所以是没有被算过的,要减去11

这样的话,所有点在这个序列中出现的总次数,也就是这个序列的长度,就是

len=i=1nxi+1=i=1nxi+n=n1+n=2n1len=\sum\limits_{i=1}^{n}x_i+1=\sum\limits_{i=1}^nx_i+n=n-1+n=2n-1

完事

好了,回归正题,既然有了欧拉序列,我们就可以把树上问题转化成序列问题了

不过问题来了,你怎么知道这就是 RMQ 呢?

我们来看,对于任意两点uuvv,设它们第一次出现的位置的序号为posupos_uposvpos_v,且posu<posvpos_u<pos_v(大不了如果不满足的话可以把uuvv换一下嘛,不影响),那么在posupos_uposvpos_v之间,深度最浅的点是哪个?

LCA(u,v)\text{LCA}(u,v)

这个可以结合 Tarjan 算法的并查集合并来想,uu要么是vv的祖先,要么不是(因为uu在序列中先出现,所以如果有一个点是对方的祖先的话,那么uu一定深度更浅,也就一定是对方的祖先),如果是的话,由于vvuu的子树上的点,所以在vv第一次出现的时候,uu的子树一定还没有搜完,也就不可能回溯到比uu更浅的点,所以在这段区间中,uu的深度一定是最浅的。如果不是,那么uuvv一定处在LCA(u,v)\text{LCA}(u,v)的两棵不同的子树上,而在搜完自己所有的子树前,LCA(u,v)\text{LCA}(u,v)是不会回溯的,所以它也是这段区间中最浅的点,所以,对于任意两个点uu和点vvposu<posvpos_u<pos_v),我们只需要找到在序列中posupos_uposvpos_v之间的深度最小的点,就可以找到它们的 LCA,而这很明显就是 RMQ

那么为什么非要取每个点第一次出现的位置来作为区间的起讫点呢(不然你想取第几个啊喂)?其实主要还是为了方便,因为有的点只会出现一次嘛,所以记录第一次出现的位置是最方便的了(当然也有可能是其他原因,不过我不太清楚,如果哪位大佬知道可以在评论里说一下)

知道以上几点之后,思路就很简单了,我们先 DFS 一遍,求出欧拉序列,然后预处理 ST 表,最后查询就完事了

参考代码

这玩意的代码比较难懂,我个人其实也不是很喜欢用

另外,这里面的 ST 表数组(也就是那个 dp)记录的其实是序列中从iii+2j1i+2^j-1这个区间里的点中具有最小深度的点在这个序列中的下标,并不是最小深度,因为我们只关心这个点是哪个点,而不关心它的具体深度

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
70
71
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
int next;
int to;
};
Edge edge[1000001];
int n,m,s,cnt,k,head[500001],f[1000001],dep[1000001],p[500001],dp[1000001][21];
//f 是欧拉序列,dep 是序列中每个位置的点的深度,p 是每个点在这个序列中第一次出现的位置
void add_edge(int u,int v)
{
cnt++;
edge[cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
}
void dfs(int u,int father,int depth)
{
k++;
dep[k]=depth;
f[k]=u;
p[u]=k;//这是从父亲节点下来的那一次,所以一定是这个点在序列中第一次出现
for(int i=head[u];i;i=edge[i].next)
if(edge[i].to!=father)
{
dfs(edge[i].to,u,depth+1);
k++;//搜完一棵子树回溯时也要记录
dep[k]=depth;
f[k]=u;
}
}
void RMQ()//ST 表初始化
{
for(int i=1;i<=2*n-1;i++)
dp[i][0]=i;
for(int i=1;(1<<i)<=2*n-1;i++)
for(int j=1;j+(1<<i)-1<=2*n-1;j++)
{
int a=dp[j][i-1],b=dp[j+(1<<(i-1))][i-1];
dp[j][i]=dep[a]<dep[b]? a:b;//记录下标,而不是深度
}
}
int query(int l,int r)//查询
{
int t=log(r-l)/log(2.0);
int a=dp[l][t],b=dp[r-(1<<t)+1][t];
return dep[a]<dep[b]? f[a]:f[b];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
dfs(s,0,1);
RMQ();
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",query(min(p[a],p[b]),max(p[a],p[b])));//这里就相当于调换顺序
//当然也可以在函数中比较两者大小
//如果前大后小,就调换顺序
}
return 0;
}

相关题目

LCA 其实也不算多难的算法吧,但这玩意如果是和其他东西结合起来,可以让人觉得十分恶心,所以还是应该加强训练,提高自己的水平

【笔记】图论-最近公共祖先

http://www.azusemisa.top/posts/1889299791.html

作者

AzuSemisa

发布于

2020-07-19

更新于

2020-10-02

许可协议

评论