最近公共祖先LCA

蔚落 2023-01-17 08:29 135阅读 0赞

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

![20210428101522339.png][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 1][]

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

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

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

& 原理1 暴力搜索法

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

1．向上标记法

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 2][]

2．同步前进法

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 3][]

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。

![20210428101713747.png][]

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*\]。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 4][]

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

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\]。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 5][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 6][]

总结：按照增量递减的方式，到达的节点深度比*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\]。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 7][]

（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\]。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 8][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 9][]

总结：按照增量递减的方式，到达的节点相同时，什么也不做；到达的节点不同时，同时上移，直到增量为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*(*n*log*n*)时间，每次查询都需要*O*(log*n*)时间。一次建表、多次使用，该算法是基于倍增思想的动态规划，适用于多次查询的情况。若只有几次查询，则预处理需要*O*(*n*log*n*)时间，还不如暴力搜索快。

[20210428101522339.png]: /images/20221021/8b91cd96919f43b3877f10dcd23b09e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70]: /images/20221021/18add596e915449dadbc318673299b24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 1]: /images/20221021/cb5ffac5f2c24cacaac787e7cb0c9d3e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 2]: /images/20221021/8589af007d624716a93fde6ce932985d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 3]: /images/20221021/d9b84e927a154ead8b2a9761636159ec.png
[20210428101713747.png]: /images/20221021/f59d9759d0a043728358493d3b6f7049.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 4]: /images/20221021/858fc1d546a743be9613fb985700dae3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 5]: /images/20221021/c9e1c834e88d476d834bc488689bb8b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 6]: /images/20221021/d3f2a94d8e344529887af8af6fa2a4a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 7]: /images/20221021/9afee07430d842668e7a1b8489af3164.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 8]: /images/20221021/2044fd77eb1a40218313503ea9370bda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 9]: /images/20221021/633e0d4eb5e647bd86f41d348ad6ba83.png