# LCA: Lowest common ancestor 最近公共祖先

# 倍增求 LCA

预处理向上跳 2^k 步的结果 f [k][x] O(nlogn)O(n \log n)

求的时候先把两个点跳到一个深度,这里有一个特判,如果重合直接返回这个点

然后 log 值从大往小枚举,两个点一起不断向上跳,直至父亲相同,直接返回父节点

可以O(n)O(n) 预处理 log 值,把复杂度降到 O(常数)O(常数)


# 欧拉序求 LCA

欧拉序:dfs 时的访问完整路径,回溯时也要把这个点算上

易知欧拉序的长度是 2n-1,从边的角度考虑,每条边都是来回访问了两次,加上根节点的初始访问,2 (n-1)+1=2n-1

这里就是一个小性质,记 p [i] 为 i 节点在欧拉序中第一次出现的位置,则对任意的 u,v,在 ol [p [u]..p [v]] 段内,使 p [ol [i]] 最小的 ol [i] 即为 lca (u,v)

多次询问可用 ST 表预处理最小值 O(nlogn)O(n \log n) 预处理,O(1)O(1) 查询

(刚发现我的 ST 表之前一直带 log 查询的。。。


# Tarjan 求 LCA

# 树剖求 LCA

更新于