树上背包学习笔记
树上背包学习笔记做完洛谷P2014实在心绪澎湃，感觉对树上背包有点感触所以分享一下心得
以洛谷P2014为例
我们设状态dp为以u为根节点，只从前j个子树中选m个点的最大学分
那么这个问题就和01背包很像了，不过对于每个子树（每个物品）还要枚举它可能的不同学分（价值）
即在这个子树中选几个点
这么说更像是一个子树代表好几个物品
所以总的来说就是一个01背包了
那么就可以注意到滚动数组优化
第二维可以省略掉
<strong>状态转移方程：dp = max(dp, dp] + v + dp);（k >n>>m; for(int i = 1;i >a>>b; add(a, i, b); } dfs(0, m); cout
页:
[1]