最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。

u和v的公共祖先指一个节点既是u的祖先，又是v的祖先。u和v的最近公共祖先指距离u和v最近的公共祖先。若v是u的祖先，则u和v的最近公共祖先是v。

可以使用LCA求解树上任意两点之间的距离。求u和v之间的距离时，若u和v的最近公共祖先为lca，则u和v之间的距离为u到树根的距离加上v到树根的距离减去2倍的lca到树根的距离：dist[u]+dist[v]-2×dist[lca]。

求解LCA的方法有很多，包括暴力搜索法、树上倍增法、在线RMQ算法、离线Tarjan算法和树链剖分。

在线算法：以序列化方式一个一个地处理输入，也就是说，在开始时并不需要知道所有输入，在解决一个问题后立即输出结果。

离线算法：在开始时已知问题的所有输入数据，可以一次性回答所有问题。

& 原理1 暴力搜索法

暴力搜索法有两种：向上标记法和同步前进法。

1．向上标记法

从u向上一直到根节点，标记所有经过的节点；若v已被标记，则v节点为LCA(u, v)；否则v也向上走，第1次遇到已标记的节点时，该节点为LCA(u, v)。

2．同步前进法

将u、v中较深的节点向上走到和深度较浅的节点同一深度，然后两个点一起向上走，直到走到同一个节点，该节点就是u、v的最近公共祖先，记作LCA(u,v)。若较深的节点u到达v的同一深度时，那个节点正好是v，则v节点为LCA(u, v)。

3．算法分析

以暴力搜索法求解LCA，两种方法的时间复杂度在最坏情况下均为O(n)。

& 原理2 树上倍增法

树上倍增法不仅可以解决LCA问题，还可以解决很多其他问题，掌握树上倍增法是很有必要的。

F[i, j]表示i的2^j辈祖先，即i节点向根节点走2^j步到达的节点。

u节点向上走20步，则为u的父节点x，F[u,0]=x；向上走2^1步，到达y，F[u,1]=y；向上走2^2步，到达z，F[u,2]=z；向上走2^3步，节点不存在，令F[u,3]=0。

F[i, j]表示i的2^j辈祖先，即i节点向根节点走2^j步到达的节点。可以分两个步骤：i节点先向根节点走2^j-1步得到F[i, j-1]；再从F[i, j-1]节点出发向根节点走2^j-1步，得到F[F[i, j-1], j-1]，该节点为F[i, j]。

递推公式：F[i, j]=F[F[i, j-1], j-1]，i=1,2,…n，j=0,1,2,…k，2^k≤n，k=log2n。

1．算法设计

（1）创建ST。

（2）利用ST求解LCA。

2．完美图解

和前面暴力搜索中的同步前进法一样，先让深度大的节点y向上走到与x同一深度，然后x、y一起向上走。和暴力搜索不同的是，向上走是按照倍增思想走的，不是一步一步向上走的，因此速度较快。

问题一：怎么让深度大的节点y向上走到与x同一深度呢？

假设y的深度比x的深度大，需要y向上走到与x同一深度，k=3，则求解过程如下。

（1）y向上走2^3步，到达的节点深度比x的深度小，什么也不做。

（2）减少增量，y向上走2^2步，此时到达的节点深度比x的深度大，y上移，y=F[y][2]。

（3）减少增量，y向上走2^1步，此时到达的节点深度与x的深度相等，y上移，y=F[y][1]。

（4）减少增量，y向上走2^0步，到达的节点深度比x的深度小，什么也不做。此时x、y在同一深度。

总结：按照增量递减的方式，到达的节点深度比x的深度小时，什么也不做；到达的节点深度大于或等于x的深度时，y上移，直到增量为0，此时x、y在同一深度。

问题二：x、y一起向上走，怎么找最近的公共祖先呢？

假设x、y已到达同一深度，现在一起向上走，k=3，则其求解过程如下。

（1）x、y同时向上走2^3步，到达的节点相同，什么也不做。

（2）减少增量，x、y同时向上走2^2步，此时到达的节点不同，x、y上移，x=F[x][2]，y=F[y][2]。

（3）减少增量，x、y同时向上走2^1步，此时到达的节点不同，x、y上移，x=F[x][1]，y=F[y][1]。

（4）减少增量，x、y同时向上走2^0步，此时到达的节点相同，什么也不做。

此时x、y的父节点为最近公共祖先节点，即LCA(x, y)=F[x][0]。

完整的求解过程如下图所示。

总结：按照增量递减的方式，到达的节点相同时，什么也不做；到达的节点不同时，同时上移，直到增量为0。此时x、y的父节点为公共祖先节点。

3．算法实现

void ST_create(){//构造ST
	for(int j=1;j<=k;j++)
		for(int i=1;i<=n;i++)//i先走2^(j-1)步到达F[i][j-1]，再走2^(j-1)步
			F[i][j]=F[F[i][j-1]][j-1];
}

int LCA_st_query(int x,int y) {//求x、y的最近公共祖先
	if(d[x]>d[y])//保证x的深度小于或等于y 
		swap(x,y);
	for(int i=k;i>=0;i--)//y向上走到与x同一深度 
		if(d[F[y][i]]>=d[x])
			y=F[y][i];
	if(x==y)
		return x;
	for(int i=k;i>=0;i--)//x、y一起向上走
		if(F[x][i]!=F[y][i])
			x=F[x][i],y=F[y][i];
	return F[x][0];//返回x的父节点
}

4．算法分析

采用树上倍增法求解LCA，创建ST需要O(nlogn)时间，每次查询都需要O(logn)时间。一次建表、多次使用，该算法是基于倍增思想的动态规划，适用于多次查询的情况。若只有几次查询，则预处理需要O(nlogn)时间，还不如暴力搜索快。