树上背包学习笔记

树上背包学习笔记

做完洛谷P2014实在心绪澎湃，感觉对树上背包有点感触所以分享一下心得



以洛谷P2014为例
我们设状态dp[j][m]为以u为根节点，只从前j个子树中选m个点的最大学分
那么这个问题就和01背包很像了，不过对于每个子树（每个物品）还要枚举它可能的不同学分（价值）
即在这个子树中选几个点
这么说更像是一个子树代表好几个物品
所以总的来说就是一个01背包了
那么就可以注意到滚动数组优化
第二维可以省略掉

<strong>状态转移方程：dp[j] = max(dp[j], dp[to][k - 1] + v + dp[j - k]);（k >n>>m;        for(int i = 1;i >a>>b;                add(a, i, b);        }        dfs(0, m);        cout