求 LCA 方法总结

前言

求 LCA 是十分基础的东西，但是方法众多。此篇介绍 OI 中常用的求法。

倍增求 LCA

蒟蒻最先学的求 LCA 方法就是倍增求 LCA。预处理和查询时间复杂度均为单 \(\log\)。优点为好理解，比较简单，且便于处理路径数据。

树剖 LCA

重链剖分。优点是预处理是线性复杂度，单次查询单 \(\log\) 但常数较小。且套线段树就可以方便地处理很多信息。

大致过程

先做重链剖分。求 \(lca(u,v)\)，若 \(u,v\) 在同一条链上，深度较大的那个点就是答案，否则跳离链头较远的点。

dfs 序求 LCA

参考这篇博客。

将 DFS 序求 LCA 发扬光大，让欧拉序求 LCA 成为时代的眼泪！

预处理使用 st 表，时间单 \(\log\)，但是比欧拉序少一半常数，空间也少一半常数。

大致过程

st 表处理区间父亲深度最小的结点的父亲编号。询问的时候，若 \(u=v\)，需要特判。否则设 \(dfn_u < dfn_v\)，返回时间戳在 \(dfn_u+1 \sim dfn_v\) 的结点中父亲深度最小的结点的父亲编号。正确性详见上面提到的博客。