题解 P2014 【选课】

Planet6174 · 2019-02-26 18:23:06 · 题解

我过来口胡一下 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 ，欢迎大家来玩~