全方位木DP
Typical DP Contest N - 木 Typical DP Contest N - 木 問題概要 解説 問題概要 問題へのリンク 解説 まんまこれ。 AtCoder Beginner Contest 160 F - Distributing Integers 実はというと、当問題の答えは、類題の答えの半分になります。なぜかというと、辺…
F - Distributing Integers F - Distributing Integers 問題概要 方針 k = 1パート 更新パート 実装 類題 タイトルの上に全方位DPタグがあると思うので、そこから類題を探してもいいと思います。類題が見たくない人は実装の下まで見ないように注意してくださ…
Educational DP Contest / DP まとめコンテスト V - Subtree rerootingをします。全方位DPとも呼ばれているらしいです。 問題へのリンク 解説 rerootingをします。dp[i]: iを黒にしたときのiの部分木のパターン数とすると、根が0の場合の計算がdfsでできる。…
F - Maximum White Subtree 問題概要 木に黒白の色が割り当てられていて、ある頂点を含む部分グラフにおいて白の数と黒の数の差を最大化してください。 解説 rerootingという概念らしいです。まず根が0も場合についてdpをします。 この計算自体はO(N)で終わ…
