Euler Tour (1) DFS 順に探索して、通った頂点の列を記録する($1,2,3,4,3,2,5,2,1,6,1$)。 (2) 各頂点 $i$ について、最初に通った時刻と最後に通った時刻 $\mathrm{in}[i]$, $\mathrm{out}[i]$ を覚える。 参考: ・アリ本 p. 294 (Euler Tour の名前は出ていませんが)Euler Tour による LCA の計算。 登場する頂点を並べますが、計算で必要になるのはむしろ、$\mathrm{in}[i]$, $\mathrm{out}[i]$ の方ですね。例えば閉区間 $[\mathrm{in}[i], \mathrm{out}[i]]$ を見ると、$i$ を根とする部分木 $\mathrm{subtree}_i$ の頂点が分かるという特徴があります。木に対する主要な計算のいくつかを、区間に対する計算