思路分析

有依赖的背包类树形dp总结

一：状态表示：

考虑根节点和孩子之间的关系，dp[i][j] 表示以i为根分配j那么大的体积的最大价值

二：题型分类：

1:边作为体积的写法:

https://www.acwing.com/problem/content/1076/

void dfs(int u, int fa){
    for(int i = h[u];~i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;
        dfs(k, u);
        for(int j = m;j >= 0;--j)
            for(int t = 0;t <= j-1;++t)
                dp[u][j] = max(dp[u][j], dp[u][j-t-1] + dp[k][t] + w[i]);
    }
}

2:顶点的数量或者顶点的权值作为体积：

（1）： https://www.acwing.com/problem/content/288/

void dfs(int u){
    for(int i = h[u];~i;i = ne[i]){//物品组
        int k = v[i];
        dfs(k);
        for(int j = m-1;j >= 0;--j)//背包容量
            for(int t = 1;t <= j;++t)//决策组内的选择
                dp[u][j] = max(dp[u][j], dp[u][j-t] + dp[k][t]);
    }
    for(int j = m;j >= 0;--j) dp[u][j] = dp[u][j-1] + w[u];
}

(2) : https://www.acwing.com/problem/content/10/

void dfs(int u){
    for(int i = h[u];~i;i = ne[i]){
        int k = e[i];
        dfs(k);
        for(int j = m-v[u];j >= 0;--j)
            for(int t = 1;t <= j;++t)
                dp[u][j] = max(dp[u][j], dp[u][j-t] + dp[k][t]);
    }
    //j 从m到0
    for(int j = m;j >= v[u];--j) dp[u][j] = dp[u][j-v[u]] + w[u];
    for(int j = 0;j < v[u];++j) dp[u][j] = 0;
}

本题完整代码

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = N * 2;

int idx, h[N], v[M], ne[M];
int w[N];
int dp[N][N];
int n, m;

void add(int a, int b, int c){
    ++idx;v[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx;
}

void dfs(int u, int fa){
    for(int i = h[u];~i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;
        dfs(k, u);
        for(int j = m;j >= 0;--j)
            for(int t = 0;t <= j-1;++t)
                dp[u][j] = max(dp[u][j], dp[u][j-t-1] + dp[k][t] + w[i]);
    }
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0;i < n - 1;++i){
        int a, b, c;cin >> a >> b >> c;
        add(a, b, c);add(b, a, c);
    }
    dfs(1, -1);
    cout << dp[1][m] << endl;
}