【問題集】木DPの入門
AtCoder
AtCoder500点
ABC-F
青色diff
木
木DP
DP
DP状態空間を絞る
最大スコア
制約条件:グラフの次数列
Greedy
グラフ
【問題集】木DPの入門
【問題集】木DPのステップアップ
最適化問題
木 DP のいい感じの練習問題だった！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる (重みは負のこともある)。 この木の辺の部分集合であって、各頂点 に接続する辺の本数が 本以下であるようなものに対して、辺の重みの総和の最大値を求めよ。 …
yukicoder
木
木DP
Greedy
木上の最大マッチング問題
葉から考える
最大安定集合・最小点被覆・最小辺被覆
最大安定集合問題
グラフ
NP困難(特殊構造なので解ける)
最適化テク:解を変形していく(最適性を失わずに)
けんちょん本演習問題
【問題集】DPのステップアップ
【問題集】木DPの入門
そのまま覚えたいシンプル設定の中堅以上の典型問題
いわゆる「木上の最大安定集合問題」です！ 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてくだ…
