泛化物品优化树上背包

概念

泛化物品优化树上背包是一种利用”泛化物品”思想来优化 树上背包 DP 时间复杂度的技巧。树上背包的朴素做法是对树上每个节点做背包合并，总时间复杂度为 $O(n\cdot m^2)$（$n$ 为节点数，$m$ 为背包容量）。通过泛化物品的合并方式，可以将复杂度优化到 $O(nm)$。

核心思想

泛化物品

在背包问题中，一个”泛化物品”可以看作一个函数 $h(v)$，表示分配费用 $v$ 时能获得的最大价值。普通的 0-1 物品、完全背包物品都是泛化物品的特例。

两个泛化物品 $f$ 和 $g$ 的合并定义为：

$h(v)={\max }_{0\le k\le v}\{f(k)+g(v-k)\}$

这是一次 $O(m)$ 的卷积操作。

树上背包的优化

树上背包的关键观察是：朴素合并中，每个节点需要与所有子树逐一做背包合并。如果不加优化，外层枚举子树、内层枚举容量，看似是 $O(n{m}^2)$。但利用以下性质可以证明复杂度实际为 $O(nm)$：

• 每对节点 $(u,v)$ 在合并过程中最多贡献一次计算——当且仅当在它们的 LCA 处合并时。
• 因此总的合并操作量等价于所有节点对的贡献之和，为 $O(nm)$。

具体实现时，按 DFS 序处理子树，依次将每个子节点的泛化物品与当前节点的结果合并即可。

时间复杂度

方法	时间复杂度
朴素树上背包	$O(n{m}^2)$（未优化枚举上界时）
泛化物品优化	$O(nm)$

适用场景

• 树形依赖背包问题（选择某个物品前必须选择其父节点）
• 树上分组背包、树上多叉背包
• 需要在树结构上做背包 DP 且 $m$ 较大的场景

参考

• 洛谷 - 泛化物品优化树上背包