オイラーツアーをすると、木に対する計算から区間の計算に言い換えができる。

区間の話にできると、例えばセグ木などのツールが使える。

オイラーツアーには、頂点に注目したものと、辺に注目したものの2種類がある。

頂点に着目したオイラーツアー

• 木に対して3つ組 (tour, in, out) を計算する。
  • tour: ある種の DFS 訪問順
  • in[v]: 頂点 v を最初に通った時刻
  • out[v]: 頂点 vを最後に通った時刻 (出ていった時刻にするケースもある)
• オイラーツアーの使い方
  • tour[in[v]..=out[v]] : 頂点 v を根に持つ部分木
  • tour[0..=in[v]]: 根 0 から 頂点 v までのパス（遠回りしてる可能性もある）
  • tour[in[u]..=in[v]] : 2つの頂点 u, v を含む部分木 (in[u] <= in[v] の場合)
    • LCA で出てくる (LCA)

出ていった時刻を考える場合は in[v]..out[v] のような区間を考えることになる。

辺に着目したオイラーツアー

参考

• Euler Tour のお勉強 | maspyのHP
  • 辺に着目したオイラーツアー
• 高難易度木問題を解くテクニック集 - Speaker Deck

メモ

• 変更がなければオイラーツアーしなくても木DPでよさそう。ある種の変更クエリがある場合はオイラーツアーしてセグ木するみたいな話になりそう。