nm的树上背包

nao_nao · 2020-03-10 18:27:47 · 个人记录

我们都会树上背包 nm^2 的做法，非常简单 （不是） ，我们只需要在每一个节点上都做一次背包即可。然而，遇到数据范围更大的树上背包，这显然是不可过的。

我们有复杂度优秀到 nm 的做法。

先挂神犇博客

我们先来造一棵树当例子（出来吧，皮卡丘！）

为了使用 nm 的奇技淫巧，我们要对树上节点进行重编号，编号为它的后序遍历序。

所以我们的树变成了这样子：

这个后序遍历序也显然有和dfs序相同的一点性质，就是同一子树的序肯定是连续的。并且可以发现，子树的根是最后加的。

我们可以按照现在点的编号来加边，dp[i][j] 表示前 i 个点中选取 j 个所得到的最大价值。

我们在每一次加点的时候，可以有选与不选两种选择。如果选此点的话，我们有 dp[i][j] = dp[i-1][j-1]+s[i]，如果我们不选此点，那么显然我们也不能选它的子树，所以我们有 dp[i][j] = dp[i-siz[i]][j]，两者取\max即可。

虽说如此，还是要看图（图多漂亮）

我们来看一下加进去前六个点时的图：

然后继续加点：

有了这些图，你是不是能更好的理解了？

如果此文有所帮助（包括图），请点个赞吧！