Day 165-Q3 — 2026-09-29 | 木上の連結な K 頂点で重み最大（木ナップサックと min(size, K) の上界）

📋 コピーimport sys
NEG = -(1 << 60)
def main():
    data = sys.stdin.buffer.read().split()
    n, K = int(data[0]), int(data[1])
    w = [int(x) for x in data[2:2 + n]]
    adj = [[] for _ in range(n)]
    p = 2 + n
    for _ in range(n - 1):
        u = int(data[p]) - 1; v = int(data[p + 1]) - 1; p += 2
        adj[u].append(v); adj[v].append(u)
    # 根 0 から順序と親を求める（再帰を使わない）
    parent = [-1] * n; order = [0]
    for v in order:
        for c in adj[v]:
            if c != parent[v]:
                parent[c] = v; order.append(c)
    # f[v][j] = v を含み部分木内に収まる連結な j 頂点集合の重み最大（j=1..min(size,K)）。添字 0 は未使用
    f = [None] * n
    best = NEG
    for v in reversed(order):
        cur = [NEG, w[v]]                       # j=1 は v だけ
        for c in adj[v]:
            if c == parent[v]: continue
            fc = f[c]; f[c] = None              # 使い終わった子の表は捨ててメモリを抑える
            # 子を使わない（そのまま）か、子の側から b>=1 頂点を足す
            new = cur + [NEG] * (min(len(cur) - 1 + len(fc) - 1, K) - (len(cur) - 1))
            for a in range(1, len(cur)):
                ca = cur[a]
                if ca == NEG: continue
                lim = min(len(fc) - 1, K - a)
                for b in range(1, lim + 1):
                    t = ca + fc[b]
                    if t > new[a + b]: new[a + b] = t
            cur = new
        f[v] = cur
        if len(cur) > K and cur[K] > best: best = cur[K]
    print(best)
main()