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

hamayanhamayan's blog

競技プログラミングにおける全方位木DP問題まとめ

全方位木DP

  • 全方角木DPとも言ったりする
  • 普通の木DPはその頂点を根とした"部分"木についての性質を表すdp
  • 全方位木DPはその頂点を根とした木全体についての性質を表すdp

基本的にDFSを2回回すことで全方位木を作る。
具体的には1回目のDFSで普通の木DPを作り、2回目のDFSで今までの経路の情報とさっき作った木DPを用いて全方位木DPを行っていく。

使える問題としては、木の全ての頂点について、そこを根として考えたパターンを考える必要がある場合に全方位木DP的な考え方ができる場合がある。

問題

Codeforces Round #405 D. Bear and Tree Jumps

http://codeforces.com/contest/791/problem/D

square869120Contest #4 D. Driving on a Tree

http://s8pc-4.contest.atcoder.jp/tasks/s8pc_4_d

AIM Tech Round 3 (Div. 1) C. Centroids

http://codeforces.com/contest/708/problem/C

Codeforces Round #395 (Div. 1) D. Timofey and a flat tree

http://codeforces.com/contest/763/problem/D














解説

CS Academy: Connected Tree Subgraphs

https://csacademy.com/contest/archive/#task/connected-tree-subgraphs/
恐らく最も一般的な全方位木DPの例。
pekempeyさんの解説の図が全てを物語ってる感ある。
http://pekempey.hatenablog.com/entry/2016/08/25/200759

Codeforces Round #397 E. Tree Folding

http://codeforces.com/contest/765/problem/E
len[i] : 頂点iの部分木を1つのパスにした時の長さ
can[i] : 頂点iの部分木を1つのパスにできるか
を1回目のdfsで普通の木DPして、2回目のdfsで全方位的にlenとcanを更新しながら、答えも更新していく。

AIM Tech Round 3 (Div. 1) C. Centroids

http://codeforces.com/contest/708/problem/C
全方位木的な考え方をする前提で考えていても分からない。
まだ解けてない。
http://tozangezan.hatenablog.com/entry/2017/01/04/234106
http://mayokoex.hatenablog.com/entry/2016/09/03/185037
http://pekempey.hatenablog.com/entry/2016/08/25/150855

Codeforces Round #395 (Div. 1) D. Timofey and a flat tree

http://codeforces.com/contest/763/problem/D
木の同型判定についてのハッシュを全方位的に作っていく問題。
とにかくむずい。