【算法详解】LCA（最近公共祖先）_lca算法详细讲解

定义：

Lca（最近公共祖先） 指在一棵有根树中任意$2$个节点$u,v$最近的公共祖先。
如下图：

如右图，结点$4，6$的公共祖先有$1、2$，但最近的公共祖先是$2$，即$Lca(4,6)=2$。
如何求得$u,v$的最近公共祖先呢？

算法一：暴力

现在有一个最朴素的算法，暴力。

• $1$.u，v中深度大的往上走，直到$u，v$深度相同。若此时$u==v$，则已找到，输出$u$。
• $2$.如果深度相同$u,v$却没有相等，就令$u，v$一起往上走，直到走到同一个结点，输出$u$。

算法时间复杂度为$O(n)$。

代码如下：

int Lca(int u,int v)
{
   
	//fa 表示每个节点的父亲
	//dep 表示每个节点深度 
	//dep，fa数组都可以预处理出来 
	if (fep[u]>dep[v]) swap(u,v);
	while (dep[v]>dep[u]) v=fa[v];
	//令v,u在同一深度 
	if (u==v) return u;
	while (u!=v)
	{
   
		u=fa[u];
		v=fa[v];	
	} 
	return u;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

算法二：倍增法

思想：注意到$u，v$向上走到最近公共祖先$w$之前，$u，v$所在的结点不相同。而到达最近公共祖先$w$后，再往上走仍是$u，v$的公共祖先，即$u，v$走到同一个结点。这具有二分性质。于是我们可以预处理出一个