本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-04 18:22:38

典型的树形背包，比如 P2014 选课，其复杂度是 $O(nm^2)$ 的。但实际上，我们可以达到 $O(nm)$ 的优秀复杂度。

常规的做法是：对每一个节点，我们计算它子树在 $0$ 到 $m$ 上的最优值，然后枚举每一个子节点被分配给的空间大小，并求得最值。

我们考虑优化：不将节点看作是树形的，而是将它摊平。对某一个点 $p$ 的子节点 $q$，它的初始值是 $p$ 在当前的值。也就是说，将这个树摊平之后，$p$ 成为第 $i$ 个节点，而它的孩子 $q$ 是第 $i + d$ 个，我们有 $f(i+d)_0 = f(i)$。

在转移时，我们不需要考虑“给某个子节点分配多大的空间”，因为它们此时都是并列的。在总空间为 $t$ 时，给这个孩子的便是 $t - 1$。

于是最后的复杂度就是 $O(nm)$ 的。