定义

给定一棵有根树，若节点 z 既是节点 x 的祖先，也是节点 y 的祖先，则称 z 是 x,y 的公共祖先。在 x,y 的所有公共祖先中，深度最大的一个称为 x,y 的最近公共祖先，记为 LCA(x,y)。

LCA(x,y) 是 x 到根的路径与 y 到根的路径的交会点。它也是 x 与 y 之间的路径上深度最小的节点。求最近公共祖先的方法通常有三种：

向上标记法

从 x 向上走到根节点，并标注所有经过的节点。

从 y 向上走到根节点，当第一次遇到已标记的节点时，就找到了 LCA(x,y)。

对于每个询问，向上标记法的时间复杂度最坏为 O(n)。

树上倍增法

树上倍增法是一个很重要的算法。除了求 LCA 之外，它在很多问题中都有广泛应用。设 F[x,k] 表示 x 的 2^k 辈祖先，即从 x 向根节点走 2^k 步到达的节点。特别地，若该节点不存在，则令 F[x,k]=0。F[x,0] 就是 x 的父节点。除此之外，任意k∈[1,logn]，F[x,k]=F[F[x,k-1],k-1]。

这类似于一个动态规划的过程，“阶段”就是节点的深度。因此，我们可以对树进行广度优先遍历，按照层次顺序，在节点入队之前，计算它在 F 数组中相应的值。

以上部分是预处理，时间复杂度为 O(nlogn)，之后可以多次对不同的 x,y 计算 LCA，每次询问的时间复杂度为 O(logn)。

基于 F 数组计算 LCA(x,y) 分为以下几步：

1. 设 d[x] 表示 x 的深度。不妨设 d[x]≥d[y]（否则可交换 x,y）。

2. 用二进制拆分思想，把 x 向上调整到与 y 同一深度。

具体来说，就是依次尝试从 x 向上走 k=2^logn,...,2^1,2^0 布，检查到达的节点是否比 y 深。在每次检查中，若是，则令 x = F[x,k]。

3. 若此时 x=y，说明已经找到了 LCA，LCA 就等于 y。

4. 用二进制拆分思想，把 x,y 同时向上调整，并保存深度一致且二者不相会。

具体来说，就是依次尝试把 x,y 同时向上走 k=2^logn,...,2^1,2^0 步，在每次尝试中，若 F[x,k]≠F[y,k] (即仍未相会)，则令 x=F[x,k],y=F[y,k]。

5. 此时 x,y 必定只差一步就相会了，它们的父节点 F[x,0] 就是 LCA。

LCA的Tarjan算法

Tarjan 算法本质上是使用并查集对“向上标记法”的优化。它是一个离线算法，需要把 m 个询问一次性读入，统一计算，最后统一输出。时间复杂度为 O(n+m)。

在深度优先遍历的任意时刻，树中节点分为三类：

1. 已经访问完毕并且回溯的节点。在这些节点上标记一个整数 2。

2.已经开始递归，但尚未回溯的节点。这些节点就是当前正在访问的节点 x 以及 x 的祖先。在这些节点上标记一个整数 1。

3. 尚未访问的节点。这些节点没有标记。

对于正在访问的节点 x，它到根节点的路径已经标记为 1。若 y 是已经访问完毕并且回溯的节点，则 LCA(x,y) 就是从 y 向上走到根，第一个遇到的标记为 1 的节点。

可以利用并查集进行优化，当一个节点获得整数 2 的标记时，把它所在的集合合并到它的父节点所在的集合中(合并时它的父节点标记一定为 1，且单独构成一个集合)。

这相当于每个完成回溯的节点都有一个指针指向它的父节点，只需查询 y 所在集合的代表元素(并查集的get操作)，就等价于从 y 向上一直走到一个开始递归但尚未回溯的节点(具有标记1)，即 LCA(x,y)。

题目示例

题目链接

代码示例

#include
#include
#include
#include
#include
using namespace std;
 
const int maxn=1010000;
int n;
int m;
int s;
int tot;
int head[maxn];
int lg[maxn];
int depth[maxn];
int fa[maxn][32];
 
struct edge{
	int to;
	int from;
	int nxt;
}e[2*maxn];
 
void add(int x,int y){
	tot++;
	e[tot].to=y;
	e[tot].from=x;
	e[tot].nxt=head[x];
	head[x]=tot;
}
 
void dfs(int now,int fath){
	fa[now][0]=fath;
	depth[now]=depth[fath]+1;
	for(int i=1;i<=lg[depth[now]];i++) fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fath) continue;
		dfs(y,now);
	}
}
 
int lca(int x,int y){
	if(depth[x]swap(x,y);
	while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];
	if(x==y) return x;
	for(int k=lg[depth[x]]-1;k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
 
int x,y;
 
int main(){
	cin>>n>>m>>s;
	for(int i=1;i
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<-1]==i);
	dfs(s,0);
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		cout<<lca(x,y)<
	}
}