树的 Euler Tour 技巧

三种序列 ​

深度优先搜索公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。的 preorder 让每节点出现一次；记录 (tin,tout) 后，

$$u\in subtree(v)⟺tin(v)\le tin(u)<tout(v).$$

DFS 返回前会完整处理孩子子树，因此子树连续。Entry/exit 序列每节点两次，适合进入加、退出减；完整 Euler walk 每条边走两次，长 $2n-1$，相邻深度差 $\pm 1$，用于 LCA 的 RMQ。

真例 ​

根 1 的孩子为 2、3，2 的孩子为 4、5。preorder ((1,2,4,5,3)) 中子树 2 是半开区间 ([1,4))；数组区间加便等价于子树加。完整 walk 含返回的父节点，不能套同一端点。

无根树须先选根；换根改变祖先关系，link/cut 会破坏静态次序。动态 Euler-tour tree 是维护序列的数据结构，不是一次 DFS 数组。

对子树和可令扁平数组 (\operatorname{flat}[tin(v)]=weight(v))；任意路径通常还需 LCA 或重链分解，不能硬写成一个 preorder 区间。完整 Euler walk 中节点多次出现，LCA 归约要固定首次位置；混用 preorder 下标与 walk 下标会产生真实错答。

对该树，4 与 3 的首次出现区间中最浅节点为 1，故 LCA 为 1；4 与 5 的对应区间最浅节点为 2。若使用 preorder 深度，回退父节点的记录消失，RMQ 归约会错。

三种序列的生成过程 ​

DFS 进入 $v$ 时设置 $tin(v)$ 并把 $v$ 加入 preorder；遍历完所有孩子后设置 $tout(v)$。Entry/exit 差分还在进入处写 $+v$、退出处写 $-v$。完整 walk 则在从孩子返回父亲时再次写父亲，因此边 $(u,v)$ 对应向下和向上两次相邻转移。

例树完整 walk $(1,2,4,2,5,2,1,3,1)$ 中，子树 2 的 preorder 区间是 $(2,4,5)$，但 walk 片段含重复 2。不同数组服务不同查询，不能因都叫 Euler Tour 共用长度和端点。

子树与路径的数组化 ​

令 flat$[tin(v)]=weight(v)$，则子树和为半开区间和。对子树加、点查询，可在差分数组的 $tin(v)$ 加 $\mathrm{\Delta }$、$tout(v)$ 减 $\mathrm{\Delta }$；点 $u$ 的前缀和正累计所有祖先子树更新。

任意 $u$–$v$ 路径不是一个 preorder 区间。离线点权路径和可用根前缀 $P(u)+P(v)-2P(lca)+weight(lca)$；动态一般需重链或动态树。Euler 技巧只完成线性化，后续结构决定成本。

静态失效构造 ​

在根 1 下原有子树 2 的区间连续；执行 cut$(1,2)$ 再 link$(2,3)$ 后，旧 preorder 中 2 的节点不一定落在 3 的区间。继续更新旧区间会改错节点。动态 Euler-tour tree维护的是可拼接序列，另有平衡树不变量。

参考资料

• Cormen et al., Introduction to Algorithms, DFS timestamps.
• Bender, Farach-Colton, “The LCA Problem Revisited,” 2000.