ST 表 LCA
\(O(n\log n)\) 预处理，\(O(1)\) 查询。空间 \(O(n\log n)\)
考虑欧拉序，设 \(dfn[u]\) 为点 \(u\) 在欧拉序中第一次出现的位置
不妨设 \(dfn[u]<dfn[v]\)，\(lca(u,v)\) 即为 \([dfn[u],dfn[v]]\) 中深度（或者 \(dfn\)）最小的点
剩下的问题是静态 RMQ，ST 表解决
优化
欧拉序长度是 \(2n-1\)，但询问的端点只有 \(n\) 个，这为优化提供了可能
考虑相邻的两个端点 \(u,v\)（即“第一次 dfs 到”\(u\) 后第一个“第一次 dfs 到”的点是 \(v\)），我们希望知道 \([dfn[u]+1,dfn[v]]\) 中 \(dfn\) 最小的结点从而把这一段缩起来，下证这个点是 \(fa[v]\)
- \(u\) 是 \(v\) 的祖先：一定有 \(u=fa[v]\)，否则 \(u,v\) 之间的点都是“第一次 dfs 到”
- 否则：
dfs的过程一定是从 \(u\) 回溯到 \(lca(u,v)\)，再一步走到 \(v\)
具体实现看代码比较好懂
标签：log,dfs,fa,dfn,LCA,欧拉 From： https://www.cnblogs.com/ft61/p/17929543.html