DFS 序求 LCA

很冷门的科技，但是有着显著的使用效果（减少建立虚树的常数）。

本文学习自：Alex_Wei 的博客

首先遍历一遍整棵树，可以得到整棵树的 DFS 序和每个点的时间戳（记为 \(dfn\) ）。

考虑两个点 \(u,v\) ，求这两个点的 LCA 。不妨设 \(dfn_u<dfn_v\) 。

• 若 \(u\) 不是两个点的 LCA。考虑 DFS 序的过程，从根开始，先到 LCA ，然后到 \(u\) 所属的子树，回溯到 LCA ，最后到 \(v\) 所属的子树。可以看出，DFS 序上 \([dfn_u,dfn_v]\) 之间是没有深度小于等于 LCA 的点的，而且所有点都在 \(u\rightarrow v\) 的路径上。所以我们可以尝试去找 DFS 序上 \([dfn_u,dfn _v]\) 之间的深度最小的点，这个点一定是 LCA 的某一个儿子。那么 LCA 也就可以求出来了。
• 若 \(u\) 就是 LCA ，显然有很多种做法来求，但是我们为了统一和美观，我们其实考虑 DFS 序上 \([dfn_u+1,dfn_v]\) 这段区间即可。这样子问题就转化为了上一种情况。
• 唯一需要特判的情况就是 \(u=v\) 的情况。

上面的过程只需要一个 \(\rm ST\) 表即可。复杂度为 \(\mathcal O(n\log n)-\mathcal O(1)\)

P3379 代码