オイラーツアー
- 木をDFSしたときの順番で頂点を記録する手法
- pre-order : 頂点に到着したら記録
- post-order : 頂点から離れるときに記録
- 用途
- 根付き木のある頂点からの部分木に対するクエリを処理
- ある頂点がある頂点の部分木に含まれるかを高速に判定する
- 上手くオイラーツアーを作るとパスのコストの総和が取れる
- 木をBFSしたときの順番で頂点を記録するBFS Euler Tourというのもある
問題
- DFS Euler Tour
- ECR6 New Year Tree Euler Tour + 遅延セグ木(区間set,区間or)
- TCO 2015 Round1B Hard TheTipsTheTreeAndMan 用途2
- SRM 621 Div1 Med TreesAnalysis 用途2
- CF200 Water Tree Euler Tour + 遅延セグ木(区間set,区間総和) + セグメント木(最大値)
- CF232 On Changing Tree Euler Tour + BIT + imos法
- CF225 Propagating tree Euler Tour + BIT
- AtCoder 根付き木のみさわさん Euler Tour + LCA (考察が難しい)
- (難）AtCoder 白黒ツリー Euler Tour + BIT + LCA
- RUPC2015 F. Tree/木 Euler Tour + BIT
- CF442 Danil and a Part-time Job Euler Tour+遅延セグ木(バイナリでの区間xor,区間sum)
- RUPC2017 Day3 ブロッコリー？カリフラワー？ (Broccoli or Cauliflower) 解説
- BFS Euler Tour
オイラーツアーっぽくやる問題
- 頂点に入ったら操作をして、出るときに逆操作をする系の問題
