痕伯 发表于 2025-8-12 16:14:00

树上背包学习笔记

树上背包学习笔记

做完洛谷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

磁呃泵 发表于 2025-10-9 10:25:48

懂技术并乐意极积无私分享的人越来越少。珍惜

篁瞑普 发表于 2025-10-11 17:03:08

这个好，看起来很实用

怃膝镁 发表于 2025-11-26 22:58:44

收藏一下   不知道什么时候能用到

蜴间囝 发表于 2025-12-4 14:00:21

感谢，下载保存了

咚獭 发表于 2025-12-10 11:43:34

yyds。多谢分享

郦湘云 发表于 2025-12-31 17:25:47

前排留名，哈哈哈

吟氅 发表于 2026-1-5 06:01:32

过来提前占个楼

艾晓梅 发表于 2026-1-8 11:30:11

很好很强大我过来先占个楼 待编辑

龙骋唧 发表于 2026-1-10 06:34:32

这个好，看起来很实用

乐敬 发表于 2026-1-14 21:50:10

谢谢分享，试用一下

揿纰潦 发表于 2026-1-14 23:50:17

懂技术并乐意极积无私分享的人越来越少。珍惜

明思义 发表于 2026-1-19 06:00:07

感谢分享

向梦桐 发表于 2026-1-21 16:40:17

喜欢鼓捣这些软件，现在用得少，谢谢分享！

渭茱瀑 发表于 2026-1-22 15:34:29

不错，里面软件多更新就更好了

昝梓菱 发表于 2026-1-24 03:28:56

感谢，下载保存了

尚腱埂 发表于 2026-1-25 11:25:38

鼓励转贴优秀软件安全工具和文档！

皇甫佳文 发表于 2026-1-26 10:13:22

前排留名，哈哈哈

晁红叶 发表于 2026-1-29 07:40:33

前排留名，哈哈哈

何玲 发表于 2026-2-2 03:21:20

感谢，下载保存了
页: [1] 2
查看完整版本: 树上背包学习笔记