图论:LCA

0001-01-01
1分钟阅读时长

LCA: Lowest common ancestor最近公共祖先

倍增求LCA

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

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

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

可以$O(n)$预处理log值,把复杂度降到 $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(n \log n)$ 预处理,$O(1)$ 查询

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


Tarjan求LCA

树剖求LCA

上一页 图论
下一页 图论:Tarjan