图论/数据结构专题-学习笔记：树上最近公共祖先（LCA）
1. 前言
树上最近公共祖先（LCA），是一种图论算法，可以快速得到 有根树 中任意两个节点的最近公共祖先。
目前作者已经了解并且学会的有两种写法：
- 倍增写法求 LCA。
这种写法是最便于新手理解的，也是入门写法。
前置知识：树的基础知识（存储，DFS 遍历），然后只需要学过一小点递推思维即可。当然学过 ST 表这种基于倍增的数据结构更好。 - 树链剖分求 LCA。
这种写法比倍增少一个 log，当然常数稍微有一点大。
P.S. 写的好常数还是很小的。
前置知识：树的基础知识（存储，DFS 遍历），树链剖分。
本篇博文两种写法都会讲。
2. 倍增写法求 LCA
模板：P3379 【模板】最近公共祖先（LCA）
2.1 原理解释
不管样例，我们首先上一张图。
接下来的所有讲解结合上面这张图。
倍增算法求 LCA 的关键就是利用可倍增性。
什么意思呢？通常情况下倍增算法是可以组合的，也就是说如果我们知道相邻两端长度为 \(l\) 的贡献，就可以直接组合出这一整段的贡献。
那么放到这里是什么意思呢？
我们设 \(f_{i,j}\) 表示第 \(i\) 个节点 向上跳 \(2^j\) 步所到达的节点。 如果超出根节点限制就默认为根节点。
特别提醒：是跳 \(2^j\) 步而不是跳 \(j\) 步。
比如 \(f_{7,1}=2,f_{11,2}=1\)。
那么可倍增性是什么意思呢？考虑这个式子：
\[f_{i,j}=f_{f_{i,j-1},j-1} \]也就是说，\(i\) 先向上跳 \(2^{j-1}\) 步，再向上跳 \(2^{j-1}\) 步，等价于直接向上跳 \(2^j\) 步。
如果学过 ST 表这个式子很简单，没学过理解一下也没问题。
于是我们首先一遍 dfs 确定 \(f_{i,0}\) 和深度（为什么？后面会讲）。
然后考虑求 LCA。
求 \(x,y\) 的 LCA 首先需要将 \(x,y\) 提到相同深度。为什么？这样便于控制，使得 \(x,y\) 到 LCA 的距离相等。
接下来以及代码中总是规定 \(x\) 深度较大。
于是我们可以通过下面的简单循环将 \(x\) 提到同一深度。
for (int i = 20; i >= 0; --i)
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
然后，分两种情况：
如果此时 \(x=y\)，直接返回 \(x\) 即可。
如果此时 \(x \ne y\)：
我们需要同时跳 \(x,y\)，不断往上跳，从大到小跳，如果发现跳上去的祖先是一样的就不跳，否则就跳。最后答案为 \(f_{x,0}\)。
上面这些话你肯定看不懂，直接拿例子来说明吧。
比如我们要求 16,11 的 LCA。
先提到同一深度，因为已经在同一深度了，那么不需要操作。循环等于白执行。
然后从大到小往上跳，枚举 \(i \in [20,0]\)。
注意这里的书写是不符合区间书写规范的，但是为了便于理解从大到小往上跳，将 \([0,20]\) 写作 \([20,0]\)。
枚举中……
\(i=2\) 时，发现：\(f_{16,2}=f_{11,2}=1\)，此时不能跳，因为可能我们会漏过中间一些点（比如真正的 LCA 2 就被我们跳过了），不能挑。
\(i=1\) 时，发现：\(f_{16,1}=5,f_{11,1}=6,f_{16,1} \ne f_{11,1}\)，此时就要跳上去，因为在这两条路上不可能有点是他们的 LCA 了，需要跳上去缩小答案范围。
\(i=0\) 时，发现：\(f_{5,0}=f_{6,0}=2\)，此时根据个人喜好选择跳或不跳。
这句话是什么意思呢？为什么这个时候就可以根据个人喜好了呢？
啊，是这样的：
其实你模拟一下上面的过程，就会发现这很像二进制拆分。
当我们拆分到 \(i=0\) 也就是个位的时候，相当于我们直接取这两个节点的父节点，此时父节点一定是 LCA。那么这个时候跳不跳就无所谓了。
如果你选择了跳，那么最后答案就是 \(x\)。
如果你选择了不跳，那么最后答案是 \(f_{x,0}\)。
本人一般采取的是第二种写法。
所以结合图片，应该理解了吧。
2.2 时空复杂度分析
关于时间复杂度：
一遍 dfs 为 \(O(n)\)。
建立 \(f\) 数组为 \(O(n \log n)\)。
当然代码里面的 20 是手动设定的，真实情况是 \(\log n\)。
单独求两个点的 LCA 是 \(\log n\)，结合询问数就是 \(m \log n\)。
因此时间复杂度为 \(O(n + n \log n + m \log n)\)。
由于 \(n,m\) 同阶，可以简记为 \(O(n \log n)\)。
关于空间复杂度：
存图的空间复杂度是 \(O(n)\)。
\(dep\) 数组（记录深度）是 \(O(n)\)。
\(f\) 数组是 \(O(n \log n)\)。
因此空间复杂度为 \(O(n + n + n \log n)\)，即 \(O(n \log n)\)。
2.3 代码
代码中还是有很多细节性的问题需要注意，全部用注释标出来了。
代码：
/*
========= Plozia =========
Author:Plozia
Problem:P3379 【模板】最近公共祖先（LCA）
Date:2021/3/8
========= Plozia =========
*/
#include
using std::vector;
typedef long long LL;
const int MAXN = 5e5 + 10;
int n, m, f[MAXN][21], dep[MAXN], root;
vector Next[MAXN];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == 1) ? sum : -sum;
}
void dfs(int now, int fa, int depth)
{
dep[now] = depth;//记录深度
f[now][0] = fa;//初始化 f 数组
for (int i = 0; i < Next[now].size(); ++i)
{
int u = Next[now][i];
if (u == fa) continue;
dfs(u, now, depth + 1);
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y]) std::swap(x, y);//保证 x 深度较大
for (int i = 20; i >= 0; --i)
if (dep[f[x][i]] >= dep[y]) x = f[x][i];//提到同一深度
if (x == y) return x;//特判
for (int i = 20; i >= 0; --i)
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];//特别小心！不能拿深度判断，应该直接判断节点是否相同
return f[x][0];//最后答案不能写错
}
int main()
{
n = read(), m = read(), root = read();
for (int i = 1; i < n; ++i)
{
int x = read(), y = read();
Next[x].push_back(y), Next[y].push_back(x);
}
dfs(root, root, 1);
for (int j = 1; j <= 20; ++j)//注意循环顺序！
for (int i = 1; i <= n; ++i)
f[i][j] = f[f[i][j - 1]][j - 1];//递推
for (int i = 1; i <= m; ++i)
{
int x = read(), y = read();
printf("%d\n", lca(x, y));
}
return 0;
}
总结一下：
倍增求 LCA 的步骤就是：
- 做一遍深 搜，确定深度以及初始化 \(f\) 数组。
- 建 立 \(f\) 数组。
- 将两个节点 提 到同一深度。
- 同时往上 跳 ，最后找到答案。
可以简记为四字大法：搜建提跳。
3. 树链剖分求 LCA
树链剖分求解 LCA？首先你需要学过树剖。
没有学过？传送门：算法学习笔记：树链剖分
下面假设你已经学会了树剖。
那么树剖求 LCA 还是比较简单的吧，不同于倍增算法的 搜建提跳 四字大法，树剖只需要处理出每一个节点的顶端节点就可以做了呀。
在往上跳的时候，仍然遵循一般树剖往上跳的原则，当两个点在同一条重链的时候，深度较小的点就是答案。
代码：
/*
========= Plozia =========
Author:Plozia
Problem:P3379 【模板】最近公共祖先（LCA）
Date:2021/3/18
========= Plozia =========
*/
#include
typedef long long LL;
const int MAXN = 5e5 + 10;
int n, m, root, cnt, Head[MAXN];
int Son[MAXN], Size[MAXN], dep[MAXN], fa[MAXN], Top[MAXN];
struct node {int to, Next;} Edge[MAXN << 1];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == 1) ? sum : -sum;
}
void add_Edge(int x, int y) {Edge[++cnt] = (node){y, Head[x]}; Head[x] = cnt;}
void dfs1(int now, int father, int depth)
{
Size[now] = 1; fa[now] = father; dep[now] = depth;
for (int i = Head[now]; i; i = Edge[i].Next)
{
int u = Edge[i].to;
if (u == father) continue;
dfs1(u, now, depth + 1);
Size[now] += Size[u];
if (Size[u] > Size[Son[now]]) Son[now] = u;
}
}
void dfs2(int now, int top_father)
{
Top[now] = top_father;
if (!Son[now]) return ; dfs2(Son[now], top_father);
for (int i = Head[now]; i; i = Edge[i].Next)
{
int u = Edge[i].to;
if (u == Son[now] || u == fa[now]) continue;
dfs2(u, u);
}
}
int LCA(int x, int y)
{
while (Top[x] != Top[y])
{
if (dep[Top[x]] < dep[Top[y]]) std::swap(x, y);
x = fa[Top[x]];
}
return (dep[x] < dep[y]) ? x : y;
}
int main()
{
n = read(), m = read(), root = read();
for (int i = 1; i < n; ++i)
{
int x = read(), y = read();
add_Edge(x, y); add_Edge(y, x);
}
dfs1(root, root, 1); dfs2(root, root);
for (int i = 1; i <= m; ++i)
{
int x = read(), y = read();
printf("%d\n", LCA(x, y));
}
return 0;
}
4. 两者时间复杂度分析
对于倍增：
搜：\(O(n)\)。
建：\(O(n \log n)\)。
提与跳：单次询问为 \(O(2\log n)\)，结合 \(m\) 次询问为 \(O(2m \log n)\)。
总时间复杂度：\(O(n + n \log n + 2m \log n)=O(n \log n + m \log n)\)。
如果 \(n,m\) 同阶，则可以简记为 \(O(n \log n)\)。
对于树链剖分：
两次 dfs：\(O(2n)\)。
查找 LCA：单次复杂度 \(O(\log n)\)，结合 \(m\) 次询问为 \(O(m \log n)\)。
总时间复杂度：\(O(2n + m \log n)=O(m \log n)\)。
同样的，如果 \(n,m\) 同阶，可以记为 \(O(n \log n)\)。
5. 总结
倍增求解 LCA：搜建提跳。
树剖求解 LCA：正常找顶端节点。