前置知识：树

概念

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

举个例子，这是一棵树：

一棵树

其中，LCA(3,12)=2\text{LCA}(3,12)=2，LCA(11,12)=4\text{LCA}(11,12)=4，LCA(10,14)=1\text{LCA}(10,14)=1，LCA(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(log⁡n)O(\log n)（特殊情况另当别论）

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

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

假设这个点的深度为depudep_u，它的祖先节点的深度为depvdep_v，那么要跳到vv去，之间会经过depu−depv+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了

另外这个数组有一个递推公式，思路也比较简单，就是自己的第2i−12^{i-1}个父亲的第2i−12^{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]，所以在每次循环时判断一下就好了

还有一点，在最后这里uu和vv一起跳的时候，这个循环的顺序和移动uu到vv的深度时的顺序是相反的，也就是说这里要把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就是求log⁡n\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]=2和fa[13][0]=6，这下才能执行u=fa[u][i],v=fa[v][i]的程序，两个点分别变为22和66
  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(nlog⁡n)O(n\log n)预处理，O(log⁡n)O(\log n)查询，同时这个nn一般来说最大也就是1e51e5左右，而log⁡n\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？？？

因为在这个过程中，我们是先遍历完所有子树才把自己合并到父亲节点上，此时我们分两种情况讨论，如果uu和vv互相都不是对方的祖先，那么它们就处在两棵不同的子树上，如果遍历到vv时发现uu已经被遍历过了，那么此时uu的并查集的祖宗一定在uu和vv所属的子树分叉的地方，因为这个点的子树还没有遍历完，还差vv这棵，所以自然也就不会合并到自己的父亲上去，而这个分叉的地方很明显就是LCA(u,v)\text{LCA}(u,v)。如果uu和vv中某一个点是对方的祖先（假设vv是uu的祖先），那就更好办了，当遍历到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有询问关系的33和22，发现它们都还没有标记，所以不管，标记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，发现已经被打了标记，所以查看其祖宗，为点11（fa5=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(nlog⁡n)O(n\log n)，而询问只需要O(1)O(1)，不过有点难想，最重要的就是怎样把求 LCA 转化成 RMQ，以及为什么这样做是对的，搞懂了这一点后，代码其实就好写了

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

思路

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

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

以上面 Tarjan 算法那张图为例

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

序号 1 2 3 4 5 6 7 8 9 10 11 12 13
点 1 2 5 2 1 3 7 3 8 3 1 4 1

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

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

容易得出

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

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

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

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

完事

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

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

我们来看，对于任意两点uu和vv，设它们第一次出现的位置的序号为posupos_u和posvpos_v，且posu<posvpos_u<pos_v（大不了如果不满足的话可以把uu和vv换一下嘛，不影响），那么在posupos_u和posvpos_v之间，深度最浅的点是哪个？

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

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

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

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

参考代码

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

另外，这里面的 ST 表数组（也就是那个 dp）记录的其实是序列中从ii到i+2j−1i+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 其实也不算多难的算法吧，但这玩意如果是和其他东西结合起来，可以让人觉得十分恶心，所以还是应该加强训练，提高自己的水平