P2015 二叉苹果树

题目

P2015 二叉苹果树

算法标签: 动态规划, 树上$dp$, 树上背包问题, $dfs$, 记忆化搜索

思路

题目中表示的很明确, 给出了需要保留的树枝的数量, 可以理解为背包的容量, 因此可以定义状态表示$f[i][j]$表示以$i$为根节点的子树中, 保留的树枝数量不超过$j$的所有方案中价值最大的方案, 对于当前根节点$i$来说子节点的选择是有$2^k$种的, $k$是子节点的数量

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = N << 1;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int f[N][M];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }

    dfs(1, -1);

    int ans = f[1][m];
    cout << ans << "\n";
    return 0;
}