DFS 序 O(1) 求解 LCA
为我们熟知的 \(O(n\log n)-O(1)\) 的 LCA 是欧拉序，由于它的长度较大，所以它的常数也相应的变大。
那怎么用 DFS 序求 LCA 呢？
给出结论：令 \(dfn_x<dfn_y\)，\(x,y\) 的 LCA 为 DFS 序上 \([dfn_x+1,dfn_y]\) 区间内深度最小的点的编号的父亲。
证明：
- 若 \(x,y\) 没有祖孙关系，那么包含 \(y\) 的那个 LCA 的儿子根据 DFS 序的性质一定会落在这段区间之内。
- 若 \(x\) 为 \(y\) 祖先，那么这段区间内的深度最小点一定是 DFS 序为 \(dfn_x+1\) 的那个点，根据 DFS 序性质它一定是 \(x\) 的儿子。
时间复杂度同欧拉序，\(O(n\log n)-O(1)\)，但是常数和好写程度均吊打欧拉序。
参考：https://www.luogu.com.cn/article/pu52m9ue