[算法模版]树形背包

树形01背包

树形01背包和普通背包不同点在于物品之间有相互的依赖关系。选取儿子物品的必要条件是选取了所有他的祖先。

我们考虑使用dp[i][j]代表第i个点的子树内，花费了j个容量能得到的最大权值。

伪代码：

for(int i=1;i<=son;i++){//枚举所有儿子
  dfs(son[i]);//先处理儿子
  for(int j1=m;j1>=0;j1--){//枚举当前点用掉了多少容量（正着枚举会变成完全背包）
    for(int j2=0;j2<=j1;j2++){//枚举这个儿子分配多少
      dp[i][j1]=max(dp[i][j1],dp[i][j1-j2]+dp[son[i]][j2]);//更新状态
    }
  }
}

显然，复杂度是\(O(n*m^2)\)的。

特殊情况的树形背包优化

当物品的体积全部为1时，我们可以把它优化到\(O(n^2)\)的复杂度。

来自lsj爷爷的代码：

乍一看根原来的没什么不同，但是需要注意，对于每一对点，都只会在他们的LCA被枚举到一次。可以自己想想为什么。

复杂度\(n^2\)。

例题

树形01背包优化

有一种方法可以把它优化到\(n*m\)的复杂度。

咕咕咕

参考资料

树上背包的上下界优化

【算法讲堂】【电子科技大学】【ACM】树形背包问题

将树形01背包优化到O(n*m)

[算法模版]树形背包

原文：https://www.cnblogs.com/GavinZheng/p/11519540.html