262620zzj @ 2024-11-29 21:08:26
rt，最近见到了一些树形背包题，形如对于每个点 u，需要计算 u 的子树 v 内共选 x 个点的答案（答案是方案数、最小代价等）怎么计算复杂度？
by Vector_Li @ 2024-11-29 21:09:53
@262620zzj https://liuxizai.ac.cn/archives/optimization-backpack-on-tree.html#fn:1
网站的参考文献也推荐看一下
by 船酱魔王 @ 2024-11-29 21:11:13
@262620zzj 对于一次背包合并，时间复杂度为被合并集合与新加入集合的乘积，故每个结点上的时间次数为所有儿子结点的两两乘积之和，两个结点只会在 LCA 被合并一次，因此
by Sinktank @ 2024-11-29 23:20:14
自己当时是看这篇理解的：https://ouuan.github.io/post/%E6%A0%91%E4%B8%8A%E8%83%8C%E5%8C%85%E7%9A%84%E4%B8%8A%E4%B8%8B%E7%95%8C%E4%BC%98%E5%8C%96/