P2014 [CTSC1997] 选课 分析（树形背包）

· · 个人记录

题意很明确，就是选择虚拟根的 m 个子树使得总和最大。

这也是很经典的背包问题：在每一个子树上，我们做一次背包，得到这个子树在 0 到 m 的体积上的所有最值。然后处理根：很明显，这就是一个零一背包。

树形 DP 充分利用了树状结构的天生的最优子结构性质，是十分优雅的。

虚拟根的技巧也是很优雅的，可以将本来不联通的几棵树转化为一颗。