euler tour · 归约 · O(1) 查询

欧拉序：把 LCA 归约成区间最值

树上倍增把 LCA 查询压到了 $O(\log n)$ 。要再往下压，得换一种思路，不再在树上跳，而是把树摊平成一条序列，让 LCA 变成序列上的问题。

这条路的产物不只是快，它还揭示了 LCA 与 RMQ 之间的关系：两者不是「都能用 $O(\log n)$ 解」这种表面相似，而是可以互相化归的同一个问题。本页做正方向的归约（LCA 变 RMQ），笛卡尔树做反方向的。

1 · 欧拉序

DFS 走一棵树时，每个节点会被「经过」多次：第一次进入它，以及每从一个孩子回溯回来时。

定义 1.1（euler tour） DFS 过程中每次进入节点、每次从孩子回溯到节点，都把该节点追加到序列末尾。得到的序列称为这棵树的欧拉序。

长度是定死的。 $n$ 个节点各贡献一次进入， $n-1$ 条边各贡献一次回溯，合计

|E| = n + (n - 1) = 2n - 1

换个数法结论相同。节点 $v$ 在序列里出现 $\deg^+(v) + 1$ 次（ $\deg^+$ 是孩子数），求和得 $\sum_v (\deg^+(v) + 1) = (n-1) + n$ 。13 节点的演示树给出长 25 的序列，两种数法都对得上。

与欧拉序并列记一个等长的深度序列，再记一张 $\text{first}[v]$ 表，记的是 $v$ 在序列里首次出现的下标。这两样东西一次 DFS 顺手就得到了。

这一次 DFS 必须写成迭代的。递归版在链状树上按深度递归，node v26.8.1 上实测撑到六千层就抛 RangeError，而这套结构常见的输入规模是十万到百万；同一条百万长的链，本系列的迭代版 81 毫秒跑完并给出长 1999999 的欧拉序。

2 · 深度序列相邻差恒为 ±1

欧拉序的深度序列有一条别的序列没有的性质：相邻两项相差恰好 1。

理由直接从构造来：序列里相邻的两个位置，要么是「从 $v$ 进入它的孩子」（深度 $+1$ ），要么是「从孩子回溯到 $v$ 」（深度 $-1$ ）。没有第三种可能，也不存在深度不变的相邻对。

这条性质本页用不上，但它是 $O(n)$ – $O(1)$ 方案的全部依据：笛卡尔树与 O(n)–O(1) §4 会用它把块内形态压到 $2^{b-1}$ 种。

3 · 归约

定理 3.1 设 $l = \min(\text{first}[u], \text{first}[v])$ ， $r = \max(\text{first}[u], \text{first}[v])$ 。则 $\text{LCA}(u, v)$ 是欧拉序区间 $[l, r]$ 上深度最小的那个节点。

证明记 $w = \text{LCA}(u, v)$ 。

$w$ 出现在区间内：DFS 进入 $u$ 与进入 $v$ 之间，控制流必须离开 $u$ 所在的那棵 $w$ 的子树、回到 $w$ 、再进入 $v$ 所在的子树（ $u$ 与 $v$ 在 $w$ 的不同子树里）。回到 $w$ 的那一笔就落在 $[l, r]$ 内。若 $u$ 是 $v$ 的祖先，则 $w = u$ ， $\text{first}[u]$ 本身就是区间左端。

区间内没有比 $w$ 更浅的节点： $[l, r]$ 里的每一笔都发生在「进入 $u$ 」与「进入 $v$ 」之间，这段时间里 DFS 始终在 $w$ 的子树内。它若离开了 $w$ 的子树就再也回不来，因为 DFS 离开一棵子树之后不会重新进入。子树内的节点深度都不小于 $\text{depth}[w]$ 。

两条合起来： $w$ 在区间内，且区间内最小深度就是 $\text{depth}[w]$ 。 $\blacksquare$

图 3-1 · 树、欧拉序与深度折线三者同步：蓝段是两点首次出现位置之间的区间，绿点是该段的最小深度处。可换

u

与

v

观察区间与答案。

于是 LCA 查询变成：在长 $2n-1$ 的深度数组上求区间最小值的位置，再取欧拉序里该位置的节点。用 sparse table 的下标版做这个 RMQ，查询就是 $O(1)$ 。

注 · 本节要的是 argmin 而不是 min。深度值本身没用，有用的是「谁最浅」。稀疏表改成存下标、比较时比较对应的深度值即可，递推结构一字不改。并列时取哪一个都行，因为同一区间内不可能有两个不同节点同时达到最小深度（那意味着 DFS 离开又重回了同一棵子树）。并列本身并不罕见：演示树的 78 个不同点对里有 9 对存在并列，60 节点随机树上超过一半的点对都有；但三棵随机树逐对检查下来，并列位置指向的节点始终是同一个。

4 · 代价与它的位置

预处理是一次 DFS 加一张长 $2n-1$ 的稀疏表，查询是一次比较。

$O(1)$ 查询不是免费的。序列长度翻到了 $2n-1$ ，稀疏表的 $\log$ 因子作用在这个更长的序列上： $n = 100000$ 时欧拉序版的建表比较次数是 3137858，而倍增只要 1700000，预处理贵了 1.85 倍。

图 4-1 · 三种 LCA 实现在演示树全部点对上与朴素解法的比对结果，以及各自主循环计数随

n

与

q

的变化。可改询问数

q

观察预处理与查询两侧的比重变化。

所以选择由 $q$ 与 $n$ 的相对大小定： $q$ 远小于 $n$ 时倍增的总量更小， $q$ 与 $n$ 同量级或更大时欧拉序的常数查询开始占优。

三种实现（含 Tarjan 离线）在演示树的全部 91 个点对上与朴素解法逐个相同，这是本系列测试里跨实现互验那一组的可视化版本。互验能抓到单个实现的偏差，抓不到「三个一起错」，所以朴素爬到根求交那条慢路径必须留着当真值。

5 · 参考文献

Bender, M. A., & Farach-Colton, M. (2000). The LCA problem revisited. In LATIN 2000: Theoretical Informatics (pp. 88–94). Springer.
Berkman, O., & Vishkin, U. (1993). Recursive star-tree parallel data structure. SIAM Journal on Computing, 22(2), 221–242.
cp-algorithms. Lowest Common Ancestor — Farach-Colton and Bender Algorithm. https://cp-algorithms.com/graph/lca_farachcoltonbender.html