浅谈 LCA

Colinxu2020 · 2024-12-01 13:21:45 · 算法·理论

一些定义：fa_i 为 i 的父亲，dep_i 为 i 的深度，dfn_i 为 i 的深度，euler_i 为 i 的欧拉序，\min^{f} \{S\} 为 \forall x \in S, f_x 最小的元素 x，\max^f 同理。

0. 定义

节点 u 与节点 v 的 LCA（最近公共祖先）的定义是深度最深的节点 w 满足 w 同时是 u 的祖先与 v 的祖先，记为 \operatorname{lca}(u,v)=w。

1. 求法

LCA 的求法还是挺多的，这里简要介绍几种比较有实用价值的方法。

看起来很多资料都谈到了 tarjan 求 LCA 的方法，但个人认为 tarjan 求 LCA 并不比倍增/DFS 序/欧拉序法复杂度显著优，且需要数据可以离线，而对于很多题目，即使可以离线 LCA 询问，也往往会增加代码难度，作者也没有找到有意义的推广，也并不易于理解。因此没有提及。

此处用 O(A) \sim O(B) 代表该做法需要用 O(A) 的复杂度预处理，之后用 O(B) 的复杂度处理每次询问。

1.1 朴素法

这个方法其实实用价值不那么大，但是是很多方法的基础。朴素法求 LCA 共分为两步，复杂度为 O(N) \sim O(N)。

不断让深度较深的节点跳父亲，直到两个节点的深度相同。
让两个节点同时跳父亲，直到两个节点相同，即为 LCA。

另一种实现是我们将从 x 到根的路径染色，之后找到从 y 到根的路径上深度最深的有颜色的节点即可。

1.2 倍增法

倍增法较为好写，复杂度在大部分情况下也是足够的，复杂度为 O(N \log N) \sim O(\log N)。下面默认 x 为深度较深的节点，y 为深度较浅的节点。预处理 f_{i,j} 代表 i 的第 2^j 个父亲。

对于朴素法的第一步，\forall 1 \leq i \leq \log_2 N，若 dep_{f_{x,i}} \leq dep_y，则令 x=f_{x,i} 即可，倒序循环，易证对于每个 i 至多只能这样跳一次。（否则会在 i+1 的时候跳，当 i=\log_2N 时 2^i \gt N，所以也不可能出现）

对于第二步 \forall i 若 f_{x,i} \neq f_{y,i}，则令 x=f_{x,i},y=f_{y,i} 即可，最终的 LCA 即为 f_{x,0}，需要特判若第一步后 x=y 则 LCA 为 x。

应对一些卡空间的毒瘤题目时，可以将 f_{i,j} 改为 i 的第 w^j 个父亲，其中 w 是一个较小的正整数，注意可以跳多次父亲，时间复杂度为 O(N w \log_w N) \sim O(w \log_w N)，空间复杂度为 O(N\log_wN)。

1.3 DFS 序法

DFS 序法的优势是复杂度较为优秀，常规实现的复杂度为 O(N \log N) \sim O(1)，部分优秀实现可以到达 O(N) \sim O(1)。下面令 x 为 DFS 序较小的节点，y 为 DFS 序较大的节点，w 为 \operatorname{lca}(x,y)。分情况讨论：

情况①与情况②中两个不同的式子看起来很不优雅，考虑统一两个式子，容易发现在 x 不为 y 的祖先时，即使我们令 x 为 DFS 序恰好为 dfn_x+1 的节点，我们仍然会经过至少一个 w 的子节点，且仍然只会在 w 的不含其自身的子树里行动，所以对于情况①可以直接用情况②的式子。

但这样我们需要同时维护 dep 和 dfn，看起来还是比较麻烦，但因为父亲的 dfn 最小的节点的父亲一定还是 w（dfn_x \gt dfn_y, \forall y \in \operatorname{subtree}(x), y \neq x）。我们直接用一个 ST 表，底层维护父亲编号，高层维护 dfn 最小的节点的父亲即可（st_{i,j} 代表 \min^{dfn}(fa_x, \forall i \lt dfn_x \leq i+2^j)）。就达到了预期的复杂度。用四毛子可以达到更优的复杂度，但非常麻烦。

1.4 欧拉序法

欧拉序法的复杂度与 DFS 序法一样优，但在部分题目（e.g. 区间 LCA）中需要同时记录欧拉序与 DFS 序，较为麻烦。令 p_i 为编号为 i 的节点在欧拉序中第一次出现的位置，x=\min^{p}(x,y),y=\max^p(x,y)。

结论：\operatorname{lca}(x,y) = \min^{p} \{i, i \in euler_{p_x \cdots p_y}\}。证明为 euler_{p_x \cdots p_y} 一定包含回溯时产生的 \operatorname{lca}(x,y)，且一定不包含 fa_{\operatorname{lca}(x,y)}(因为只在 \operatorname{lca}(x,y) 的子树中)。

直接用 ST 表或四毛子维护即可，复杂度为 O(N \log N) \sim O(1) 或 O(N) \sim O(1)。

1.5 树链剖分

在树上不断跳重链，直到两个节点处于同一个重链即可。复杂度为 O(N) \sim O(\log N) 且常数较小。

2. 性质

定义 \operatorname{lca}(S) 为集合 S 中所有元素的最近公共祖先。

若树上 x,y 的简单路径与 a,b 的简单路径相交，则 \operatorname{lca}(x,y) 在 a,b 的简单路径上（或反过来）。

3. 应用

3.1 关于 LCA 本身

3.1.1 [LNOI2014] LCA

3.1.1.1 题面

有一个以 0 为根的有 n 个节点的有根树，m 次询问，每次给定 l,r,x 求 \sum_{i=l}^r dep_{\operatorname{lca}(i,x)}。

3.1.1.2 题解

考虑运用朴素法求 LCA 中的思路 ②，我们将从根到 x 的路径上的所有节点染色，容易发现 dep_{\operatorname{lca}(x,y)}= 从 y 到根的路径上被染色的节点数量，依此可以做到 O(nm)，注意到我们都是路径修改与查询，考虑树链剖分与线段树。为了避免烦人的零下标，可以将所有节点编号 +1 后处理。

但这样复杂度还是不够，考虑差分，将问题转化为把 y 到根染色，之后查询 x 到根的染色节点数量。将 [l,r] 拆成两个询问 [1,r] 和 [1,l-1]，分别赋 1 与 -1 的权值，按右端点排序，每当我们遇到一个区间就在当前的线段树上查询一次，否则给当前点到根的路径 +1 即可。

[GXOI/GZOI2019] 旧词也和这题差不多，我们可以发现，我们加的一实际上是 val_i-val_{fa_i}（而本题中 val_i=dep_i，旧词中 val_i=dep_i^k），我们预处理出所有的 w_i=\sum_{j \leq i} val_j-val_{fa_j} 的值，之后对于下传标记和线段树更新时，我们不再把乘上 r-l+1，转而乘上 w_r-w_{l-1} 即可，且旧词不需要差分。

3.1.2 CF1062E Company

3.1.2.1 题面

给定一棵树，若干次询问，每次询问给定 l,r 求编号为 l \sim r 中的节点任意删去一个后剩余节点 LCA 的深度的最大值。

3.1.2.2 题解

基于 LCA 的性质 ①，可以发现区间 LCA 只和 DFS 序最小与最大的节点有关，只需要分别尝试删去 DFS 序最小的最大的节点，设删去 p，依据结论②我们可以分别求 [l,p-1] 的 LCA 与 [p+1, r] 的 LCA，之后求这两个 LCA 的 LCA 即可，注意本题中根节点的深度为 0。

3.1.3 [NOIP2024] 树上查询

3.1.3.1 题面

给定一颗以 1 为根的树，q 组询问，每次询问给定 l,r,x，之后求 [l,r] 中任意长度大于等于 x 的连续子区间的 LCA 深度的最大值。

3.2 LCA 实现树上路径问题

LCA 的此类应用大多可以被树链剖分取代，此类问题常常需要用到性质③。

树链剖分大多具有更低的思维难度与更广泛的适用性，但代价是更高的代码难度。

3.2.1 P3398 仓鼠找 sugar

3.2.1.1 题面

给定一个树，多组询问，对于每个询问给定 a,b,c,d 求 a 到 b 的简单路径与 c 到 d 的简单路径是否有交集。

3.2.1.2 题解

基于 LCA 的性质⑤可以将问题转化为判断 a 到 b 的路径是否经过 \operatorname{lca}(c,d)（c 到 d 同理），之后利用性质③倍增判断即可，具体的，分别将 a 与 b 跳祖先跳到深度与 \operatorname{lca}(c,d) 相同的节点 a',b' 若 a'=\operatorname{lca}(c,d) 或 b'=\operatorname{lca}(c,d)，就说明 a 到 b 的路径经过 \operatorname{lca}(c,d)。

作为对照，本题的树剖解法是将树上 a 到 b 的路径 +1，查询树上 c 到 d 的路径和是否为 0，之后将 a 到 b 的路径减一。

3.2.2 [USACO15DEC] Max Flow P

3.2.2.1 题面

给定一颗树，多组询问，每次给定 u,v，将树上 u,v 的简单路径经过的节点权值 +1，求最终权值。

3.2.2.2 题解

基于性质③，我们维护一个树上差分，将操作拆成 u,v 到 \operatorname{lca}(u,v) 链加，对照序列差分定义树上差分，令 dif_i=v_i-\sum v_{j}[j \in \operatorname{children}(i)]（其中 v_j 代表实际的权值），对于每个操作给 dif_u \gets dif_u+1,dif_v \gets dif_v+1,dif_{\operatorname{lca}(x,y)} \gets dif_{\operatorname{lca}(x,y)}-2，之后树上前缀和即可。

作为对照，本题的树剖解法是直接将 u 到 v 的路径 +1，最后统计一次。