树形背包的二次复杂度做法

__ryp__ · 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) 的。