競プロノート

Appearance

オイラーツアー（Euler Tour） ​

DFSの訪問順を利用して、木の各頂点の部分木を連続区間に変換するテクニック。

部分木を [in[v], out[v]) で表せるようにする。

特徴 ​

項目内容
用途部分木の区間化・部分木クエリ
前処理O(N)
部分木の区間取得O(1)
空間計算量O(N)

考え方 ​

DFSで各頂点を最初に訪問した順番を記録する。

  • in[v]：頂点vに入ったときの番号
  • out[v]：頂点vの部分木を探索し終えたときの番号
  • order[i]：DFS順でi番目の頂点

頂点vの部分木は [in[v], out[v]) に対応する。

例えば、以下の木を根0から探索する。

text
      0
     / \
    1   2
   / \
  3   4

DFS順が [0, 1, 3, 4, 2] の場合、

vin[v]out[v]
005
114
245
323
434

頂点1の部分木は [1, 4) となる。

実装 ​

cpp

使用例 ​

入力（0-indexed、根は0）

text
5
10 20 30 40 50
0 1
0 2
1 3
1 4
3
0
1
2

出力

text
150
110
30

各頂点の値は {10, 20, 30, 40, 50}。

  • 頂点0の部分木：10 + 20 + 30 + 40 + 50 = 150
  • 頂点1の部分木：20 + 40 + 50 = 110
  • 頂点2の部分木：30

典型的な使い方 ​

部分木の総和 ​

DFS順に値を並べて累積和を取れば、部分木の総和を O(1) で求められる。

cpp
vector<ll> sum(n + 1);
for (int i = 0; i < n; i++) {
    sum[i + 1] = sum[i] + a[order[i]];
}

ll ans = sum[out[v]] - sum[in[v]];

BIT・セグメント木との組み合わせ ​

頂点の値が更新される場合も、部分木を区間として扱える。

例えばACLのBITを使用する場合：

cpp
atcoder::fenwick_tree<ll> fw(n);
for (int v = 0; v < n; v++) fw.add(in[v], a[v]);

// 頂点vの値にxを加算
fw.add(in[v], x);

// 頂点vの部分木の総和
ll ans = fw.sum(in[v], out[v]);

注意点 ​

  • 部分木の区間は半開区間 [in[v], out[v])。
  • out[v] - in[v] は頂点vの部分木の頂点数。
  • DFSの訪問順なので、order[in[v]] == v が成立する。
  • 根の選び方によって部分木の範囲が変わる。
  • この実装は木を前提とし、親への逆辺を除外して探索する。
  • 再帰DFSは木が深い場合にスタックオーバーフローする可能性がある。
  • 今回は各頂点を1回だけ記録する方式。辺を往復するときにも頂点を記録するオイラーツアーとは区別する。

関連 ​

  • DFS
  • LCA
  • セグメント木
  • BIT
  • 木DP