はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるオイラーツアー問題まとめ

オイラーツアー(Euler Tour)

使う目的

  • 根付き木のある頂点からの部分木に対するクエリを処理するのに長ける
  • ある頂点がある頂点の部分木に含まれるかを高速に判定する
  • 上手くオイラーツアーを作るとパスのコストの総和が取れる

以下、問題

Educational Codeforces Round 6 E. New Year Tree

http://codeforces.com/contest/620/problem/E
Euler Tour + 遅延セグ木(区間set,区間or)

TCO 2015 Round1B Hard TheTipsTheTreeAndMan

https://community.topcoder.com/stat?c=problem_statement&pm=13717
Euler Tourを「ある頂点がある頂点の部分木に含まれるかを高速に判定する」用途で使用

SRM 621 Div1 Med TreesAnalysis

http://community.topcoder.com/stat?c=problem_statement&pm=13086
Euler Tourを「ある頂点がある頂点の部分木に含まれるかを高速に判定する」用途で使用

Codeforces Round #200 (Div. 1) D. Water Tree

http://codeforces.com/contest/343/problem/D
Euler Tour + 遅延セグ木(区間set,区間総和) + セグメント木(最大値)

Codeforces Round #232 (Div. 1) C. On Changing Tree

http://codeforces.com/contest/396/problem/C
Euler Tour + BIT + imos法

Codeforces Round #225 (Div. 1) C. Propagating tree

http://codeforces.com/contest/383/problem/C
Euler Tour + BIT

天下一プログラマーコンテスト2015本戦 F. 根付き木のみさわさん

http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_f
Euler Tour + LCA
考察が難しい。

(難)NJPC 2017 H. 白黒ツリー

http://njpc2017.contest.atcoder.jp/tasks/njpc2017_h
Euler Tour + BIT + LCA

RUPC2015 F. Tree/木
Euler Tour + BIT