两种欧拉序的区别

适用于 \(O(1)\) LCA 的欧拉序

构造方法：dfs 初次访问节点的时候的时候加入欧拉序，从某个子树访问完之后再次将该节点加入欧拉序。

大小：初次会额外访问一次根节点，并且每条边都会给两个端点贡献一次，故为 \(2n-1\)。

性质：两个节点的 LCA 在欧拉序上处于两个节点之间（虽然一个点在欧拉序上有多个位置，但是任取一个位置这个性质都是成立的），且深度在区间内所有点中是最小的。

据此我们使用 ST 表维护区间（深度）最小值即可 O(1) LCA。当然 dfs 序也能

适用于树上莫队的欧拉序

构造方法：dfs 初次访问时加入欧拉序，要往父亲回溯时再加入欧拉序。

大小：显然是 \(2n-2\)。

性质：记 \(x\) 第一次访问的时间戳在 \(fst_x\)，第二次在 \(lst_x\)，设 \(dfn_x<dfn_y\)，在 \(x\) 到 \(y\) 的链上的点在欧拉序上的区间 \([lst_x,fst_y]\) 中出现了一次，其他的点出现了两次或零次。特殊情况，当 \(\operatorname{lca}(x,y)\not=x\) 时，它们的 lca 没有出现，需要特判。

据此我们可以在处理树上链查询某些特殊问题时（可树上莫队/有两两抵消性质的信息，如异或），将树拍到欧拉序上去使用数据结构去维护。