树形dp题目总结

题目一：10. 有依赖的背包问题 - AcWing题库

题目二：1074. 二叉苹果树 - AcWing题库

解题思想：

很好的一个思想 使用体积来划分集合 然后其实思想是分组背包的思想 dfs相当与循环n 然后循环体积 然后根据分组（子树所有可能的体积）更新。

注意事项：
有依赖的背包问题这个题目的解题思路和二叉苹果树一样，都是使用树形dp来做的，但是区别就在于这个题目的体积每个点都有，但是二叉苹果树这个题目的体积根节点没有，其余的都有，所以dp更新会有区别。
有依赖的背包问题： dp[i][j]表示以i为根，用到体积不超过j的所有方案。
更新策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i = h[u]; i != -1;i = ne[i]){
    int x = e[i];
    dfs(x);
    
    //循环体积 因为我们后面需要用j - k 更新 j 所以需要到这循环
    for(int j = v1;j >=v[u];j--){
        //因为我们选了父节点 所以要k-v[u]
        for(int k = 1;k <= j - v[u];k++){
            dp[u][j] = Math.max(dp[u][j],dp[u][j-k] + dp[x][k]);
        }
    }

}
//加上根节点
for(int i = v[u];i <= v1;i++) dp[u][i] += w[u];

二叉苹果树：dp[i][j]表示以i为根，用到子树体积不超过j的所有方案。这样我们循环到叶子节点（没有子树）是没有意义的,这里面更新需要注意，我们dp[e[i]][0]表示的是只选择选择一个子节点，其他不选的价值。而不是子节点都不选。所以我们的dp[x][j-k1-1]里面是j-k1-1，这里面需要减去一个e[i]节点体积。
更新策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = h[x];i != -1;i=ne[i]){
    if(e[i] == parent) continue;
    //枚举i
    dfs(e[i],x);
    //枚举子节点选的体积 由于更新是[x][j-k1-1] 到[x][j] 所以需要倒着循环
    for(int j = k;j >= 0 ;j--){
        //枚举子节点体积 因为选子节点的话父节点肯定要选所以只能循环到j-1
        for(int k1 = 0;k1 <= j - 1;k1++){
            //这里面我们 最开始状态是 dp[x][j-1] + dp[e[i]][0] + w[i] 其实就是只选择子节点一个点
            dp[x][j] = Math.max(dp[x][j],dp[x][j-k1-1] + dp[e[i]][k1] + w[i]);
        }
    }
}