読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

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

競技プログラミング

誰かに聞いたわけじゃないので、間違っていたら指摘して頂けると助かります。

全方位木DPとは?

全方角木DPとも言ったりするが、一般に木DPはその頂点を根としたサブツリーについての性質を表すdpを書く。
しかし、全方位木DPはその頂点を根とした木全体についての性質を表すdpを作る。
子供だけではないというところに全方位感がある。

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

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

問題

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

Codeforces Round #405 D. Bear and Tree Jumps

http://codeforces.com/contest/791/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

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
木の同型判定についてのハッシュを全方位的に作っていく問題。
とにかくむずい。

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を更新しながら、答えも更新していく。