nm的树上背包

我们都会树上背包 $nm^2$ 的做法，非常简单 ~~（不是）~~ ，我们只需要在每一个节点上都做一次背包即可。然而，遇到数据范围更大的树上背包，这显然是不可过的。 我们有复杂度优秀到 $nm$ 的做法。 先挂神犇[博客](https://www.luogu.com.cn/blog/P6174/solution-p2014) 我们先来造一棵树当例子（出来吧，皮卡丘！）  为了使用 $nm$ 的~~奇技淫巧~~，我们要对树上节点进行重编号，编号为它的[后序遍历](https://baike.baidu.com/item/%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86/1214806?fr=aladdin)序。 所以我们的树变成了这样子：  这个后序遍历序也显然有和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$即可。 虽说如此，还是要看图（图多漂亮） 我们来看一下加进去前六个点时的图：  然后继续加点：      有了这些图，你是不是能更好的理解了？ 如果此文有所帮助（包括图），请点个赞吧！