题解 P2014 【选课】

我过来口胡一下 DFS 序的奇妙做法。 我们把原树叫做 A。 定义　 多叉树的**后序遍历**指的是：在搜索某个结点的过程中，先记录它的所有子树，再记录它本身。注意，如果有多个子树，则后序遍历的顺序不限。 定义　 多叉树的**后序遍历序列**指的是在上述过程中所记录下来的序列。 我们不妨在 DFS 后把结点按照后序遍历序列**重新编号**。下图就是一个例子，左图为原树 A，右图为重新编号的树 B。  现在，如果我们要复制一棵树 B（不妨称复制品为 C），将新树 B 里面的结点**按编号**（也就是按照 A 树的后序遍历序列）**依次**加入 C 中，我们会发现，**每次加入的结点在当前情况下都是根结点**。下图展示了放入 4, 7, 8, 9 号结点时，新图的情况。  因此，设 $\mathrm{dp}(i,j)$ 表示将树 B 的结点 $1\ldots i$ 放入新图，背包容量为 $j$ 时，所能取得的最大价值。设 $\mathrm{size}_i$ 表示以 $i$ 为根的子树的大小。 - 若取物品 $i$（前提是此时的背包容量放得下物品 $i$），则可以取它的子树，则 * 问题转化为「将结点 $1\ldots i-1$ 加入 C，且背包容量为 $j-1$ 时，所能取到的最大价值」加上物品 $i$ 的价值， * 所以答案为 $\mathrm{dp}(i-1,j-1)+v_i$； - 若不取物品 $i$，则不可以取它的子树，则 * 问题转化为「将『结点 $1\ldots i-1$ 中不属于 $i$ 的子树的结点』加入 C，背包容量不变时，所能取到的最大价值」 * 答案为 $\mathrm{dp}(i-\mathrm{size}_i,j)$； 综上可得 $\mathrm{dp}(i,j)=\begin{cases}\max(\mathrm{dp}(i-1,j-1)+v_i,\;\mathrm{dp}(i-\mathrm{size}_i,j)) & j\ge w_i \\ \mathrm{dp}(i-\mathrm{size}_i,j) & j<w_i \end{cases}$ 。 易证其时间复杂度为 $O(NM)$。 最后打个广告，LOJ 已上线树形背包模板题 https://loj.ac/p/160 ，欢迎大家来玩~