0 序 为了强化笔者对LCA的理解，故作此文。 1 DFS序求LCA 1.1 算法介绍 考虑树上的两个节点 $u$, $v$ 和其祖先 $d$，我们之所以使用欧拉序求解 LCA 是因为在欧拉序中 $d$ 一定在 $u,v$ 之间出现。但对于 DFS 序来说，$d$ 一定在 $u,v$ 之前出现。 令 $u$ 的 DFN 小于 $v$，且 $u\ne…