問題
$N$ 頂点の木（重み $w_v \ge 0$）で、ちょうど $K$ 頂点を選ぶ独立集合（隣接する2頂点を同時に選ばない）の重み最大値を求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 3000$ |
| $K$ | $1 \le K \le N$ |
| $w_v$ | $0 \le w_v \le 10^9$ |
入出力例
入力例 1
7 3
5 3 8 1 6 2 9
1 2
1 3
2 4
2 5
3 6
3 7出力例 1
20頂点1(w=5)、頂点5(w=6)、頂点7(w=9) を選ぶ。1-2辺で1と5は非隣接（1-2-5の経路）、1と7も非隣接。5と7も非隣接。総和=5+6+9=20。
概念図: 木DPのマージ（ナップサック型）
ヒント（段階的開示）
ヒント1: 方向性
木DPで $dp[v][j][s]$ = 「部分木 $v$ 内で $j$ 個選ぶ最大重み（$s=1$: $v$ 自身を選ぶ）」を定義。子を一つずつマージするナップサック型DP。
ヒント2: アプローチ
- 葉ノード: $dp[v][0][0] = 0$、$dp[v][1][1] = w_v$
- 子 $c$ のマージ: $s=1$ のとき $c$ は選べない（$t_c = 0$ のみ）
- $s=0$ のとき $c$ は選んでも選ばなくてもよい（$t_c \in \{0, 1\}$）
- 全体 $O(N^2)$（マージ補題: $\sum s_v \cdot s_c = O(N^2)$）
ヒント3: コード骨格
# BFS逆順（葉から根へ）
for v in reversed(order):
dp[v][0][0] = 0
dp[v][1][1] = w[v]
for c in children[v]:
new_dp = [[-INF]*2 for _ in range(K+1)]
for j1 in range(cur_sz+1):
for s in range(2):
if dp[v][j1][s] == -INF: continue
for j2 in range(sz[c]+1):
if j1+j2 > K: break
if s == 1: # v選ぶ → cは選べない
if dp[c][j2][0] != -INF:
new_dp[j1+j2][s] = max(...)
else: # v選ばない → cはどちらでも
for tc in range(2):
if dp[c][j2][tc] != -INF:
new_dp[j1+j2][s] = max(...)模範解答 (Python)
import sys
from collections import deque
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
w = [0] + list(map(int, input().split()))
adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
INF = float('-inf')
sz = [1] * (N + 1)
dp = [[[INF] * 2 for _ in range(K + 1)] for _ in range(N + 1)]
order = []
parent = [0] * (N + 1)
visited = [False] * (N + 1)
q = deque([1])
visited[1] = True
while q:
v = q.popleft()
order.append(v)
for c in adj[v]:
if not visited[c]:
visited[c] = True
parent[c] = v
q.append(c)
for v in reversed(order):
dp[v][0][0] = 0
dp[v][1][1] = w[v]
cur_sz = 1
for c in adj[v]:
if c == parent[v]:
continue
new_dp = [[INF] * 2 for _ in range(K + 1)]
for j1 in range(min(cur_sz, K) + 1):
for s in range(2):
if dp[v][j1][s] == INF:
continue
for j2 in range(min(sz[c], K - j1) + 1):
if s == 1:
if dp[c][j2][0] != INF:
val = dp[v][j1][s] + dp[c][j2][0]
if val > new_dp[j1 + j2][s]:
new_dp[j1 + j2][s] = val
else:
for tc in range(2):
if dp[c][j2][tc] != INF:
val = dp[v][j1][s] + dp[c][j2][tc]
if val > new_dp[j1 + j2][s]:
new_dp[j1 + j2][s] = val
for j in range(K + 1):
dp[v][j][0] = new_dp[j][0]
dp[v][j][1] = new_dp[j][1]
cur_sz += sz[c]
sz[v] = cur_sz
ans = max(dp[1][K][0], dp[1][K][1])
print(ans if ans != INF else -1)
solve()Step-by-Step 解説
Step 1: DP定義
$dp[v][j][s]$: 頂点 $v$ を根とする部分木内で $j$ 個を選ぶ独立集合の最大重み（$s=1$: $v$ 自身を選択）。
Step 2: 葉ノードの初期値
| 状態 | 値 |
|---|---|
| $dp[v][0][0]$ | $0$（$v$ を選ばず、0個） |
| $dp[v][1][1]$ | $w_v$（$v$ を選ぶ、1個） |
| その他 | $-\infty$（不可能） |
Step 3: 子とのマージルール
| $v$ の状態 | $c$ の状態 | 理由 |
|---|---|---|
| $s=0$（選ばない） | $t_c \in \{0,1\}$ 可 | 辺の制約なし |
| $s=1$（選ぶ） | $t_c = 0$ のみ | $v$-$c$ 辺が存在するため $c$ は選べない |
Step 4: 計算量（マージ補題）
各子 $c$ のマージコストは $O(s_v \cdot s_c \cdot K / N)$（$K$ 制約で打ち切り）。木全体でのマージの総コストは $O(N^2)$（どの2頂点ペアも高々1回マージされる）。
Step 5: 答えの読み出し
$\max(dp[1][K][0], dp[1][K][1])$ が答え。$-\infty$ なら $K$ 個の独立集合が存在しないので $-1$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 隣接制約の誤り | $s=1$ でも子を選んでしまう | $s=1$ のとき $t_c=0$ のみ加算 |
| INF初期化の方向 | 最大化なので $-\infty$ が正しい | INF = float('-inf') |
| sz[v] の更新忘れ | マージ後にサイズを加算しない | cur_sz += sz[c] を忘れずに |
| new_dpのコピー漏れ | マージ後に dp[v] を更新しない | new_dp の内容を dp[v] に反映 |
次のステップ
発展問題: $K$ を固定せず全 $K \in [1, N]$ について答えを出力。関連: 木のナップサックDP（重さと価値）、$O(NK)$ での最適実装。