一些定义：

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$ 互不为祖先关系，这种情况下我们 DFS 的顺序一定是先从 $w$ 访问到 $u$ ，再回到 $w$ ，再从 $w$ 访问 $u$ ，因此 $\forall dfn_x \leq dfn_i \leq dfn_z$ ， $i$ 在 $w$ 的子树中（不含 $w$ ）。而因为 $w$ 到 $u$ 的路径与 $w$ 到 $v$ 的路径不交，所以 $dfn_x$ 到 $dfn_y$ 中一定恰好有两个 $w$ 的儿子节点，我们取所有 $dfn_x \leq dfn_i \leq dfn_y$ 中深度最浅的节点 $i$ 的父亲，即为 LCA $w$ 。
$x$ 是 $y$ 的祖先，考虑①中的结论为什么不对，因为深度最浅的节点 $u$ 的父亲是 $fa_u$ ，所以我们会错误的算出 $w=fa_u$ 而不是 $w=u$ ，我们考虑对式子稍作修改，让深度最浅的节点变为 $x$ 到 $y$ 的路径上深度次浅的节点，容易发现只需要把式子变形为 $dfn_x \lt dfn_i \leq dfn_y$ 即可。
$x=y$ 特判即可， $w=x$ 。

情况①与情况②中两个不同的式子看起来很不优雅，考虑统一两个式子，容易发现在

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

中所有元素的最近公共祖先。

$\operatorname{lca}(S)=\operatorname{lca}(\min^{dfn}(S), \max^{dfn}(S))$ ，证明不难通过 1.3 中的结论得到，可用于优化子集的 LCA。
$\operatorname{lca}(S \cup T)=\operatorname{lca}(\operatorname{lca}(S), \operatorname{lca}(T))$ ，证明显然，是很多性质的基础。
$x$ 到 $y$ 在树上的简单路径可以分为 $\operatorname{lca(x,y)}$ 与 $x$ 的链与 $\operatorname{lca(x,y)}$ 与 $y$ 的链，证明：显然一定会经过 $\operatorname{lca}(x,y)$ ，而如果经过 $fa_{\operatorname{lca}(x,y)}$ ，则不为简单路径。
$\operatorname{lca}(x \cdots y)=\min^{dep}(\operatorname{lca}(x, x+1), \operatorname{lca}(x+1, x+2) \cdots \operatorname{lca}(y-1, y))$ ，证明基于虚树。
若树上 $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

，最后统计一次。

浅谈 LCA

文章操作