树上的分组背包

具体见代码注释.

Python 代码

from collections import defaultdict
from functools import lru_cache

@lru_cache(None)
def dp(root, V):
    # 根节点为root的子树, 并且体积不超过V的约束条件下, 能够获得的最大价值

    # 根节点的体积大于V的时候, 连更节点都无法选中, 很明显, 价值为0
    if Nodes[root][0] > V:
        return 0

    # ans: 根节点的价值
    ans = Nodes[root][1]

    # V2: 去除掉根节点后的体积
    V2 = V - Nodes[root][0]

    # 平凡的情况: 当子节点的个数小于等于1时
    if len(G[root]) == 0:
        return ans
    elif len(G[root]) == 1:
        return ans + dp(G[root][0], V2)

    # 当子节点个数 > 1时, 使用分组背包的方法
    # 每个子节点能够形成的体积, 构成一组商品.
    # 比如root下面有左儿子和右儿子.
    # 形成了2组, 每组最多选择1个"商品".
    # 这个"商品"是比较抽象的.
    # 以左儿子为例.
    # 左儿子的所有商品可能为: 
    # 总体积<=1, 价值最大化的商品组合打包为一个"商品".
    # 总体积<=2, 价值最大化的商品组合打包为一个"商品".
    # 总体积<=k, 价值最大化的商品组合打包为一个"商品".

    f = [0] * (V2 + 1)
    for i in range(len(G[root])):
        for j in range(V2, -1, -1):
            for k in range(Nodes[G[root][i]][0], j + 1):
                f[j] = max(f[j], dp(G[root][i], k) + f[j - k])
    return ans + f[V2]


N, V = map(int, input().split())
G = defaultdict(list)
Nodes = [(0, 0)] # 因为节点序号为1开始, 因此, 序号为0出填充一个垃圾节点.
for i in range(1, N + 1):
    v, w, p = map(int, input().split())
    if p == -1:
        root = i
    else:
        G[p].append(i)
    Nodes.append((v, w))

print(dp(root, V))