树的 Euler Tour 技巧

DFS 把树的嵌套结构投影到时间轴：进入一个节点后，在离开它之前发生的所有首次访问恰好属于其子树；若把沿边返回父亲的动作也记录下来，数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。深度便忠实画出树上上下移动。不同投影保留的信息不同，所以 preorder 的子树区间与完整 walk 的 LCA 区间不能混用。

真例 ​

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

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

对子树和可令扁平数组 $\mathrm{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维护的是可拼接序列，另有平衡树不变量。