图论：LCA

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

# 倍增求 LCA

预处理向上跳 $2^k$ 步的结果数组 f[k][x] 。

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

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

可以 $O(n)$ 预处理 log 值，把单次查询复杂度降到 $O(常数)$。

复杂度：预处理 $O(n \log n)$，查询 $O(1)$

# 欧拉序求 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)$

# Tarjan 求 LCA

# 树剖求 LCA