オイラーツアー Euler Tour

部分木に対するクエリとかを効率的に行いたいときに便利。
ABC294Gで学んだ。
atcoder.jp

根からdfsしたときに、辺（あるいは頂点）を通った順に記録しておく。
ついでに問題に必要な情報も同じ順番で記録しておく。
こうすると任意の部分木について、その辺（頂点）ごとの情報が連続部分列となるため、セグ木（segment tree）などで効率的にクエリを実行できる。

オイラーツアーで検索すると、少なくない人が「辺について記録した方が良い」と言っていた。
直感的な良さは今のところわかっていないが、頭の良い人が言うならたぶんそうなので、慣れるまでこの形で使ってみる。