木DP（最大独立集合）
木の上で「選ぶ / 選ばない」の 2 状態の DP 値が、葉から根へ確定していく様子を可視化します dp[v][選] , dp[v][非]。
9
55%
5
キャンバスのノードをクリックすると、その重みを
1 → 5 → 1 と切り替えて木を組み替えられます（DP は最初から再計算）。処理中のノード（葉→根）
—
確定ノード数
—
最大独立集合の重み
—
木と DP 値（緑＝採用 / 灰＝非採用、各ノード横に
[非 , 選]）
独立集合とは、どの 2 つも辺で直接つながっていないノードの集まりです。木の各ノードに重みがあるとき、重みの合計が最大になる独立集合を求めるのが最大重み独立集合問題です。
木では 木DP（根付き木の上の動的計画法）で効率よく解けます。各ノード v について、
v を選ぶなら子は選べないので子の
木では 木DP（根付き木の上の動的計画法）で効率よく解けます。各ノード v について、
dp[v][選]＝「v を選ぶ場合の、v を根とする部分木での最大重み」、
dp[v][非]＝「v を選ばない場合の最大重み」の 2 値を、葉から根へ順に確定していきます。v を選ぶなら子は選べないので子の
非、v を選ばないなら子は選んでも選ばなくてもよいので子の max(非, 選) を足します。
いま何が起きている？
ここがポイント
- 2 状態の DP ── 各ノードで「選ぶ / 選ばない」の 2 値だけ覚えれば、部分木の答えが定まる。
- 葉から根へ（後行順） ── 子がすべて確定してから親を計算するので、計算は木を下から積み上げる順になる。
- 遷移式が核心 ── 選ぶときは子の
非だけ、選ばないときは子のmax(非, 選)を足す。隣接ノードが同時に選ばれない制約はここで効く。 - 計算量は O(N) ── 各辺・各ノードを一度ずつ見るだけ。部分木サイズ（各ノードを根とする子孫数）も同じ後行順で同時に求まる。