木DP
- dp[i] := 頂点iの部分木についての何か
- Codeforcesで見つけた記事
- 全方位木DPという派生もある
- 二乗の木DPという、頂点集合のDPをマージする時に部分木の要素数の個数分だけ使ってマージするようにするとO(N^3)がO(N^2)に落ちるテクがある 元ネタ
- 木DPっぽいことをしながらマージテクを使うものもある（配列で持たずmapで持ってマージしていく）（マージテクだけど全体O(N)となる問題も存在する）
- 木DPは的確に枝刈りをしていけばなんか間に合うというケースがよくある
- 重軽再帰動的計画法という新しい木DPもある 有名で唯一の解説
- 木DPとは違うかもしれない。部分木のDPをもらってきてマージではなく、直接部分木にDPを渡して、更新して返してもらう
問題
- EDPC Independent Set 解説
- yukicoder No.763 Noelちゃんと木遊び 解説
- AC 塗り絵 解説1 解説2
- yukicoder No.417 チューリップバブル 解説1 解説2 解説3
- AtCoder 木 解説1 解説2
- HOJ tree 解説
- AtCoder うなぎ 解説1 解説2 解説3
- ARC083 Bichrome Tree 解説
- CF Helga Hufflepuff's Cup
- JAG Tree Separator 解説
- APC001 Antennas on Tree
- HE Holi And Tree（子供の個数分だけ内部でDPしているからならし間に合う）
- HE Tree and robots （DP in 木DP）
- HE Forming Teams（木DP in 木DP）
- CF551 Serval and Rooted Tree 解説
上級木DP
二乗の木DP
- yukicoder No.196 典型DP (1) 解説1 解説2
- CF Karen and Supermarket 解説1 解説2
- CF Representative Sampling
- ARC029 高橋君と木のおもちゃ 解説1 解説2 解説3
- CF Berland Federalization 解説1 解説2
- AC 特別講演「括弧列と塗り分け」 解説
- AOJ よくわかる二重魔法 解説
- HE Shubham and Tree-2
- ARC101 Ribbons on Tree 解説
- AC Attack to a Tree 解説
O(NK)の木DP
