洛谷 P2015 二叉苹果树

url: https://www.luogu.com.cn/problem/P2015

tag：
树形DP，动态规划

思路：
用数组f[u, j] 表示以u为根节点使用不超过 j 条边时最大的苹果数量。和背包问题有点不同的是，对于每一个点来说，假如需要用到某一个子节点来更新，则需要与之想连，所以其实是需要预备那个子节点所连的所有边 + 1的边来更新。所以状态转移方程为 f[u, j] = max(f[u, j], f[u, j - k - 1] + f[v,k] + w).在用二维循环更新时，不能让可能用到的边超过子树拥有的边，所以每次dfs之后还需要用s数组来更新以当前节点为根时所拥有的最大的边数。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 200;
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int n, q;
int s[N];
int f[N][N];
void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}
void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        s[u] += s[j] + 1;
        for (int l = min(s[u], q); l; l --)
            for (int k = min(s[j], l - 1); k >= 0; k --)
                f[u][l] = max(f[u][l], f[u][l - k - 1] + f[j][k] + w[i]);
    }
}
int main()
{
    cin >> n >> q;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c),add(b, a, c);
    }
    dfs(1, 0);
    cout << f[1][q] << endl;
    return 0;
}