1.有依赖的背包问题
普及组题现在还不会。。。太有实力辣。
2.P6326 Shopping
题目的要求实质上是要我们选的位置构成一个连通块。
可以暴力枚举根做树上依赖背包。
优化的方法是点分治，计算经过当前重心的连通块，不经过的可以地柜计算。
时间复杂度 \(O(nm \log n)\)。
3.P3780 [SDOI2017] 苹果树
首先这个 \(t - h \le k\) 可以转化为“免费选一条根链，求至多选 \(k\) 个的最大价值”。
考虑枚举这条根链，然后整棵树就被这条链划分成了两部分，且两部分是在 dfs 序上连续的，链上的部分可以选 \(a_i - 1\) 个，其余部分可以选 \(a_i\) 个。
不放将链上的部分合并到左边的部分，这样就可以预处理两部分的背包，然后 \(O(k)\) 查询答案。
具体来说，在 dfs 的时候，可以先放入 \(a_i - 1\) 个，然后递归儿子，合并儿子的时候再把儿子中少选的一个加上，这样算的就是对的。
时间复杂度 \(O(nk)\)
标签：背包,记录,2024.8,可以,dfs,根链,部分,复杂度 From： https://www.cnblogs.com/definieren/p/18340139