Educational DP Contest / DP まとめコンテスト (EDPC) : V - Subtree 解説動画
- jupiroさんの動画
- 木DPは理解済みとする
- rerootingという言葉を使っていて、しっくりきた
- この動画でイメージを掴んだ後に
- https://atcoder.jp/contests/dp/tasks/dp_v
- を解いたり、ei1333さんの解説Blogを読みに行くとスムーズに学べるはず
- かつっぱさん V問題 Subtree
追記：ABCで出題された！
- 2020/03/28
- F - Distributing Integers https://atcoder.jp/contests/abc160/tasks/abc160_f
- それにより全方位木DPの解説がいくつも生み出されて理解が深まる
- snukeさんのF問題解説 AtCoder Beginner Contest 160 - YouTube
- keymoonさんの解説
全方位木DP or rerooting
- snukeさんやかつっぱさんの説明だと全方位木DPという印象。各辺の矢印をすべて求めるため
- jupiroさんの説明だとrerootingという印象
全方位木DPを使う問題集（随時追記）
- D - Driving on a Tree
- https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_d
- 木。同じ点を訪れない。何歩動けるか（期待値）
- dp[i] 下方向期待値
- dp2[i] 上方向期待値
- [1800] F. Maximum White Subtree
- https://codeforces.com/contest/1324/problem/F
- AC https://codeforces.com/contest/1324/submission/92001846
- rerootingするときに左max,右maxなどを事前準備する必要のないシンプルな問題。dfs2で矢印を付け替えながら答えを求めて格納していく
- AOJ 3163 Star Gazer
- AC https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5948346#1
- snukeさん式で解いた。dfs後はdp[0]のみ正しい状態になっていて、頂点0からの矢印は全て出ているので十分な情報があり、それを利用して子たちのdpも求める
- やっと掴めた気がする
- AOJ 1595 Traffic Tree
- https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1595&lang=ja
- 深さの木DPをして、maxを取りたいので左からと右からの累積maxをとるいつものやつ。けんちょんさんの記事がある
- ABC222 F Expensive Expense
- 3月にも出たが10月にも出た。全方位木DPは半年に1度出る！
- 子たち（部分木）のmaxを取らねばならぬので左からのmax, 右からのmaxを用意しておく典型をやった
- ✅https://atcoder.jp/contests/abc222/submissions/26480824
