算法竞赛专题解析│LCA
以下文章来源于清华计算机学堂 ，作者清华计算机学堂
如果计算机是通向未来的大门，我们愿意为你打造一把打开这扇门的钥匙——清华大学出版社计算机与信息分社
本篇介绍了求LCA（最近公共祖先）的算法：树上的倍增，树上的Tarjan以及树上的差分。
在“并查集”这一篇中提到它的一个应用是求最近公共祖先（Least Common Ancestors, LCA）。求LCA是树上的一个基本计算，本节介绍包括并查集在内的多种解法。
公共祖先：在一棵有根数上，若结点F是结点x的祖先，也是结点y的祖先，那么称F是x、y的公共祖先。
最近公共祖先（LCA）：在x、y的所有公共祖先中，深度最大的那个称为最近公共祖先，记为LCA(x, y)。
▍图1 一棵树
在上图中，根节点a的深度是1，每往下一层，深度加1。求一棵树上的所有结点的深度，只需要用DFS遍历一次即可。
图中e、g的公共祖先有a、c，其中c的深度是2，a的深度是1，c的深度更大，所以c = LCA(e, g)。
显然有以下性质：
（1）在所有公共祖先中，LCA(x, y)到x和y的距离都最短。例如在e、g的所有祖先中，c距离e、g最短。
（2）x、y之间最短的路径，经过LCA(x, y)。从e到g的最短路径，经过c。
（3）x、y本身也可以是它们自己的公共祖先，例如，若y是x的祖先，则有LCA(x, y) = y。例如，图中d = LCA(d, h)。
如何求LCA？根据LCA的定义，读者很容易想到一个简单直接的方法：分别从x和y出发，一直往根结点走，第一次相遇的结点，就是LCA(x, y)。具体实现时，可以用标记法：首先从x出发一直向根结点走，沿路标记所有经过的祖先结点；把x的祖先标记完之后，然后再从y出发向根结点走，走到第一个被x标记的结点，就是LCA(x, y)。
标记法的复杂度较高，在有n个结点的树上求一次LCA(x, y)的计算量为O(n)。若有m次查询，总复杂度是O(mn)，效率太低。
经典的算法有倍增法、Tarjan算法（DFS+并查集），都能高效地求得LCA，适合做大量的查询。
倍增法的复杂度是O(nlogn + mlogn)，相当好。Tarjan算法的复杂度是O(m + n)，是最优的算法，不可能更好了。
倍增法是“在线算法”，单独处理每个询问；Tarjan是“离线算法”，需要统一处理所有询问。
另外，树链剖分也是求LCA的常用方法。
树上的倍增
前面提到的标记法可以换个方式实现，具体来说是以下两个步骤：
步骤（1）：先把x和y提到相同的深度。例如x比y深，就把x提到y的高度（即让x走到y的同一高度），如果发现y就是x的祖先，那么LCA(x, y) = y，停止查找，否则继续下一步。
步骤（2）：让x和y同步往上走，每走一步就判断是否相遇，相遇点就是LCA(x, y)，停止。
上面两个步骤，由于x和y都是慢腾腾一步一步往上走，复杂度都是O(n)的。如何改进？如果不是一步步走，而是跳着往上走，就能加快速度。如何跳？可以按2的倍数往上跳，跳1、2、4、8、…步，这就是倍增法。倍增法是常见的思路，应用很广，树上倍增求LCA是一个典型的应用。
倍增法用“跳”的方法加快了上面的两个步骤。注意已知条件是：每个结点知道它的子结点和父结点，并通过DFS计算出了每个结点在树上的深度。下面仍然按照这两个步骤解释具体算法。
步骤（1）
把x和y提到相同的深度。具体任务是：给定两个结点x、y，设x比y深，让x“跳”到与y相同的深度。注意x和y都是随机给定的，它们不是树上的特殊结点。
因为已知条件是只知道每个结点的父结点，所以如果没有其他辅助条件，x只能一步步往上走，没办法“跳”。要实现“跳”的动作，必须提前计算出一些x的祖先结点，作为x的“跳板”。然而，应该提前计算出哪些祖先结点呢？通过这些预计算出的结点，真的能准确地跳到一个任意给定的y吗？最关键的是，这些预计算是高效的吗？这就是倍增法的精妙之处：预计算出每个结点的第1、2、4、8、16、…个祖先，即以2倍增的祖先。
有了预计算出的这些祖先做跳板，能从x快速跳到任何一个给定的目标深度。注意，跳的时候先用大数再用小数。以从x跳到它的第27个祖先为例：
（1）从x跳16步，到达x的第16个祖先fa1；
（2）从fa1跳8步，到达fa1的第8个祖先fa2；
（3）从fa2跳2步到达祖先fa3；
（4）从fa3跳1步到达祖先fa4。
共跳了16+8+2+1=27步。这个方法利用了二进制的特征：任何一个数都可以由2的倍数相加得到。27的二进制是11011，其中的4个“1”的权值就是16、8、2、1。把一个数转换为二进制数时，是从最高位往最低位转换的，这就是为什么要先用大数再用小数的原因。
显然，用倍增法从x跳到某个y的复杂度是O(logn)的。
剩下的问题是如何快速预计算每个结点的这些“倍增”的祖先。定义fa[x][i]为x的第2i个祖先，有以下非常巧妙的递推关系：
fa[x][i] = fa[fa[x][i-1]][i-1]
递推式的右边这样理解：
1）fa[x][i-1]。从x起跳，先跳2i−1步到了祖先z = fa[x][i-1]；
2）fa[fa[x][i-1]][i-1] = fa[z][i-1]。再从z跳2i−1步到了祖先fa[z][i-1]。
一共跳了2i−1+2i−1=2i步。公式右边实现了从x起跳，跳到了x的第2i个祖先，这就是递推式左边的fa[x][i]。
特别地，fa[x][0]是x的第20 = 1个祖先，就是x的父结点。fa[x][0]是递推式的初始条件，从它递推出了所有的fa[x][i]。递推的计算量有多大？从任意一个结点x到根节点，最多只有logn个fa[x][]，所以只需要递推O(logn)次。计算n个结点的fa[][]，共计算O(nlogn)次。
步骤（2）
x和y同步往上跳，找到LCA。
经过步骤（1），x和y现在位于同一个深度，让它们同步往上跳，就能找到它们的公共祖先。x、y的公共祖先有很多，LCA(x, y)是距离x、y最近的那个，其他祖先都更远。以下的讨论都假设x和y深度相同。
能利用fa[][]来找LCA(x, y)吗？显然，LCA(x, y)并不一定正好位于fa[x][]和fa[y][]上，那么还能利用fa[][]数组吗？答案是确定的，其原理也用到了二进制的特征。下面介绍这个方法，可以称之为“逼近法”。
从一个结点跳到根结点，最多跳logn次。现在从x、y出发，从最大的i ≈ logn开始，跳2i步，跳到了祖先fa[x][i]、fa[y][i]，它们位于非常靠近根结点的位置（2i≈2logn≈n）。有两种情况：
1）fa[x][i] = fa[y][i]，这是一个公共祖先，它的深度小于等于LCA(x, y)，这说明跳过头了，退回去换个小的i-1重新跳一次。
2）fa[x][i] ≠ fa[y][i]，说明还没跳到公共祖先，那么更新x = fa[x][i]，y = fa[y][i]，从新的起点x、y继续开始跳。由于新的x、y的深度比原来位置的深度减少超过一半，这样再跳的时候，就不用再跳2i步，跳2i−1步就够了。
以上两种情况，分别是比LCA(x, y)的浅和深的两种位置。用i循环判断以上两种情况，就是从深和浅两头逐渐逼近LCA(x, y)。每循环一次，i减1，当i减为0时，x和y正好位于LCA的下一层，父结点fa[x][0]就是LCA(x, y)。
细节见后面模板题代码函数LCA()。
如果读者疑惑这个过程，可以模拟一个特例来理解：假设LCA(x, y)就是x和y的父结点；执行i循环（i从大到小），会发现一直有fa[x][i] = fa[y][i]，即一直跳过头；循环时i逐渐减小，而x和y一直停在原位置不动；最后i减到0，循环结束，LCA就是fa[x][0]。例如x、y的深度是27，i会从4开始循环，按照24=16、23=8、22=4、21=2、20=1的跳幅，从fa[x][4]退到fa[x][0]。
另一个特例是LCA(x, y)为整棵树的根，那么i循环时（i从大到小），一直有fa[x][i] ≠ fa[y][i]，x和y会持续往上跳；最后i = 0时，就停在根结点的下一层，仍然满足LCA = fa[x][0]。例如x、y与根结点距离27，会按照27=24+23+21+20=16+8+2+1的跳跃顺序，跳到根结点的下一层，这仍然是二进制的特征。
查找一次LCA的复杂度是多少？执行一次i循环，i从 logn递减到0，只循环O(logn)次。
倍增法的计算包括预计算fa[][]和查询m次LCA，总复杂度是O(nlogn + mlogn)。
以上分析，在“倍增与ST算法”中有非常相似的解释，两者对倍增的应用实质上一样，请对照学习。
最近公共祖先 洛谷P3379
题目描述：给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式：第一行包含三个正整数 N, M, S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N−1行每行包含两个正整数x, y，表示x结点和y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数 a, b，表示询问a结点和b结点的最近公共祖先。
输出格式：输出M行，每行包含一个正整数，依次为每一个询问的结果。
题目中树的规模很大，需要用链式前向星存储。
倍增法的代码非常简洁。代码中与倍增法有关的函数是dfs()和LCA()，前者计算结点的深度并预处理fa[][]数组，后者查询LCA。
//洛谷P3379 的倍增代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;
struct Edge{ int to, next;}edge[2*maxn]; //链式前向星
int head[2*maxn], cnt;
void init(){ //链式前向星：初始化
for(int i=0;i<2*maxn;++i){ edge[i].next = -1; head[i] = -1; }
cnt = 0;
}
void addedge(int u,int v){ //链式前向星：加边
edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++;
} //以上是链式前向星
int fa[maxn][20], deep[maxn];
void dfs(int x,int father){ //求x的深度deep[x]和fa[x][]。father是x的父结点。
deep[x] = deep[father]+1; //深度：比父结点深度多1
fa[x][0] = father; //记录父结点
for(int i=1; (1<<i) <= deep[x]; i++) //求fa[][]数组，它最多到根结点
fa[x][i] = fa[fa[x][i-1]][i-1];
for(int i=head[x]; ~i; i=edge[i].next) //遍历结点i的所有孩子。~i可以写为i!=-1
if(edge[i].to != father) //邻居：除了父亲，都是孩子
dfs(edge[i].to, x);
}
int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y); //让x位于更底层，即x的深度值更大
//（1）把x和y提到相同的深度
for(int i=19;i>=0;i--) //x最多跳19次：2^19 = 500005
if(deep[x]-(1<<i)>=deep[y]) //如果x跳过头了就换个小的i重跳
x = fa[x][i]; //如果x还没跳到y的层，就更新x继续跳
if(x==y) return x; //y就是x的祖先
//（2）x和y同步往上跳，找到LCA
for(int i=19;i>=0;i--) //如果祖先相等，说明跳过头了，换个小的i重跳
if(fa[x][i]!=fa[y][i]){ //如果祖先不等，就更新x、y继续跳
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0]; //最后x位于LCA的下一层，父结点fa[x][0]就是LCA
}
int main(){
init(); //初始化链式前向星
int n,m,root; scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++){ //读一棵树，用链式前向星存储
int u,v; scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u);
}
dfs(root,0); //计算每个结点的深度并预处理fa[][]数组
while(m--){
int a,b; scanf("%d%d",&a,&b);
printf("%d\n", LCA(a,b));
}
return 0;
}树上的Tarjan
LCA的Tarjan算法 =“DFS + 并查集”，是二者既简单又绝妙的组合。如果读者非常熟悉DFS和并查集，完全能自己推理出下面介绍的算法。
Tarjan算法是一种离线算法，它把所有的m个询问一次全部读入，统一计算，最后一起输出。Tarjan算法的效率极高，在n个结点的树上做m次LCA查询，总复杂为O(m + n)，是可能达到的最优复杂度。
如何设计一种高效的离线算法？它和在线算法不一样，不一定要单独处理每个询问，而是有条件去通盘考虑所有的询问。如果把这些询问进行某种排序之后再计算，在整体上应该能得到较好的效率。如何排序？把一个询问(x, y)看成一对结点，那么就按x排序。在树这种情况下，用DFS遍历树时，按x出现的先后为序，每处理一个x结点，就查找与x有关的结点对(x, y)，计算LCA(x, y)。
有多种DFS遍历方法，例如先序、中序、后序等，哪一种适合用来计算LCA？再次回顾标记法，它是从底层的x、y结点出发，逐步向高层的根结点走，直到第一次相遇，就是LCA(x, y)。DFS后序遍历应该很适合这种情况，后序DFS先返回最底层的叶子结点，而且是从底层结点逐层回溯到根结点，符合标记法的计算顺序。
现在以x为主，y为辅计算LCA(x, y)。
设现在遍历到了一个结点x，下面考虑结点对(x, y)的y。x和y只有两种关系：（1）y在x的子树上；（2）y不在x的子树上。
▍图2 (1)y在x的子树上 (2)y不在x的子树上
（1）y在x的子树上。即y的祖先是x，有LCA(x, y) = x。具体编程时这样做：以x为DFS的入口，因为y是在x的子树上，所以DFS后序遍历回溯先返回y，标记y为已经访问过，记vis[y] = true；后面回溯到x时，查询结点对(x, y)，若vis[y]为true，那么显然有LCA(x, y) = x。
（2）y不在x的子树上。设它们的公共祖先是u，以u为DFS的入口。DFS先访问到y，标记vis[y] = true，并在从y回溯到u的过程中，记录y的祖先结点是u，记为fa[y] = u。访问到x时，查询结点对(x, y)，若vis[y]为true，那么有LCA(x, y) = LCA(x, u) = u。读者可能注意到，若DFS先访问到x，而不是y，如何处理？忽略即可，因为x和y是成对的，后面访问到y时，再以y为主，x为辅即可。
这两种情况可以合并。在第(1)种情况中，从y回溯到x时，记录y的祖先是x，即fa[y] = x，这是情况(2)的特例。
上面的讨论，是以某个x为根，或者以某个u为根进行子树的遍历，计算出LCA(x, y)。能否扩展到整棵树，用一个DFS解决所有的LCA查询？这就是Tarjan算法的基本思路：以树的根结点为DFS入口，遍历整棵树，每遍历到一个结点，就把它看成一个x，检查x的所有结点对(x, y)的y，若vis[y] = true且fa[y] = u，那么LCA(x, y) = u。
最后还有一个关键问题没有解决：如何计算fa[y] = u？即如何在回溯过程中，把以结点u为根的子树上的所有子结点的祖先都设置为u？如果读者非常熟悉并查集，就能发现，一棵以u为根的子树，刚好是以u为集合的一个并查集。那么就容易编码了：从子树的一个结点y回溯时，把父结点fa[y]看成y的集。逐级回溯到根u的过程中，每个结点的集都记录为它的父结点。当查询y的集时，通过查找函数find_set()，最终查到y的集是u。
Tarjan算法的复杂度很好。每个结点只访问1次，每个询问也只处理一次，总复杂为O(m + n)，是可能达到的最优复杂度，不可能更好了。
//洛谷P3379 的 tarjan代码，改写自https://blog.csdn.net/Harington/article/details/105901338
#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;
int fa[maxn], head[maxn], cnt, head_query[maxn], cnt_query, ans[maxn];
bool vis[maxn];
struct Edge{ //链式前向星
int to, next, num;
}edge[2*maxn], query[2*maxn];
void init(){ //链式前向星：初始化
for(int i=0;i<2*maxn;++i){
edge[i].next = -1; head[i] = -1;
query[i].next = -1; head_query[i] = -1;
}
cnt = 0; cnt_query = 0;
}
void addedge(int u,int v){ //链式前向星：加边
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void add_query(int x, int y, int num) { //num 第几个查询
query[cnt_query].to = y;
query[cnt_query].num = num; //第几个查询
query[cnt_query].next = head_query[x];
head_query[x] = cnt_query++;
}
int find_set(int x) { //并查集查询
return fa[x] == x ? x : find_set(fa[x]);
}
void tarjan(int x){ //tarjan是一个DFS
vis[x] = true;
for(int i=head[x]; ~i; i=edge[i].next){ // ~i可以写为i!=-1
int y = edge[i].to;
if( !vis[y] ) { //遍历子结点
tarjan(y);
fa[y] = x; //合并并查集：把子结点y合并到父结点x上
}
}
for(int i = head_query[x]; ~i; i = query[i].next){ //查询所有和x有询问关系的y
int y = query[i].to;
if( vis[y]) //如果to被访问过
ans[query[i].num] = find_set(y); //LCA就是find(y)
}
}
int main () {
init();
memset(vis, 0, sizeof(vis));
int n,m,root; scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++){ //读n个结点
fa[i] = i; //并查集初始化
int u,v; scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u); //存边
}
fa[n] = n;
for(int i = 1; i <= m; ++i) { //读m个询问
int a, b; scanf("%d%d",&a,&b);
add_query(a, b, i); add_query(b, a, i); //存查询
}
tarjan(root);
for(int i = 1; i <= m; ++i) printf("%d\n",ans[i]);
}LCA的最基本应用是求树上两个结点的最短距离，它等于两点深度之和减去两倍的LCA深度：
dist(x, y) = deep[x] + deep(y) - 2*deep[LCA(x, y)]
下面给出另一个典型应用。
LCA+树上差分
Max Flow P 洛谷P3128
题目描述：有n个结点，用n-1条边连接，所有结点都连通了。给出m条路径，第i条路径从结点si到ti。每给出一条路径，路径上所有结点的权值加1。输出最大权值点的权值。
输入：第一行是n和m。后面n-1行，每行包括2个整数x, y，表示一条边。后面m行，每行2个整数s和t，表示一条路径的起点和终点。
输出：输出一个整数，表示最大权值。
树上两点u、v的路径，显然是最短路径。把u→v路径分为两部分：u→LCA( u , v )和LCA(u , v)→v。
先考虑简单的思路。首先对每个路径求LCA，分别以u和v为起点到LCA，把路径上每个结点的权值加1；然后对所有m个路径进行类似操作。把路径上每个结点加1操作的复杂度是O(n)，再乘上m次求LCA的时间，总时间会超时。
本题的关键是如何记录路径上每个结点的修改。显然，如果真的对每个结点都记录修改，肯定会超时。此时可以利用差分，差分的重要用途是“把区间问题转换为端点问题”，正适合这种情况。
给定数组a[]，定义差分数组：
D[k]=a[k]−a[k−1]，即数组相邻元素的差。
从定义推出：
这个公式描述了a和D的关系，“差分是前缀和的逆运算”，它把求a[k]转化为求D的前缀和。
对于区间[L, R]的修改问题，例如把区间内每个元素加上d。对区间的两个端点做以下操作：
（1）把D[L]加上d；
（2）把D[R+1]减去d。
▍图3 区间[L, R]上的差分数组D[]
然后求前缀和sum[x] = D[1] + D[2] + … + D[x]，有：
（1）1 ≤ x < L，前缀和sum[x]不变；
（2）L ≤ x ≤ R，前缀和sum[x]增加了d；
（3）R < x ≤ N，前缀和sum[x]不变，因为被D[R+1]中减去的d抵消了。
sum[x]等于a[x]，这样就利用差分数组计算出了区间修改后的a[x]。
从以上讨论得到一个关键的方法：利用差分，能够把区间修改问题转换为只用端点做记录。不用差分数组时，区间内每个元素都需要修改，复杂度O(n)；用差分转换为只记录两个端点后，复杂度减少到O(1)。这就是差分的重要作用。
把上述的差分概念应用在树上，只需要把树上路径转换为区间即可。把一条路径u →v分为两部分：u→LCA( u , v )和LCA(u , v)→v，这样每个路径都可以当成一个区间来处理。
记LCA( u , v ) = L，并记L的父结点为s = fa[L]，本题是把路径上每个结点权值加1：
（1）路径u→L这个区间上，D[u]++，D[s]–。
（2）路径L→v这个区间上，D[v]++，D[s]–。
经过以上操作，能通过D[]计算出u→v上每个结点的权值。不过，由于两个路径在L和S这里重合了，上面2个步骤把D[L]加了2次，把D[s]减了2次，需要调整为：D[LCA( u , v )]–和D[s]–。详情见下图。
▍图4 (1)两个线形差分 (2)合并为树上差分
在本题中，对每个路径都用倍增法求一次LCA，并做一次差分操作。当所有路径都计算完之后，再做一次DFS，求出每个结点的sum[]，即求得每个结点的权值。其中的最大值为答案。
复杂度讨论：m次LCA复杂度O(nlogn + mlogn)；最后做一次DFS，复杂度O(n)；总复杂度约O(mlogn)。
//洛谷P3128，LCA + 树上差分
#include <bits/stdc++.h>
using namespace std;
#define maxn 50010
struct Edge{int to,next;}edge[2*maxn]; //链式前向星
int head[2*maxn],D[maxn],deep[maxn],fa[maxn][20],ans,cnt;
void init();
void addedge(int u,int v);
void dfs1(int x,int father);
int LCA(int x,int y); //以上4个函数和“树上的倍增”中洛谷P3379的倍增代码完全一样
void dfs2(int u,int fath){
for (int i=head[u];~i;i=edge[i].next){ //遍历结点i的所有孩子。~i可以写为i!=-1
int e=edge[i].to;
if (e==fath) continue;
dfs2(e,u);
D[u]+=D[e];
}
Ans = max(ans,D[u]);
}
int main(){
init(); //链式前向星初始化
int n,m; scanf("%d%d",&n,&m);
for (int i=1;i<n;++i){
int u,v; scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u);
}
dfs1(1,0); //计算每个结点的深度并预处理fa[][]数组
for (int i=1; i<=m; ++i){
int a,b; scanf("%d%d",&a,&b);
int lca = LCA(a,b);
D[a]++; D[b]++; D[lca]--; D[fa[lca][0]]--; //树上差分
}
dfs2(1,0); //用差分数组求每个结点的权值
printf("%d\n",ans);
return 0;
}参考书籍