洛谷 P2015 二叉苹果树

洛谷 P2015 二叉苹果树

题目：

• 有图。转链接

题解：

• 树形dp。
• 任然是有依赖的树上背包。
• 树上背包思路可以转这篇，值得注意的是，题目中输入的是保留的边数，那么我们要将其转换成点数 = 边数 + 1

#include <iostream>
#include <cstdio>
#define N 105
using namespace std;

struct E {int next, to, dis;} e[N * 2];
int n, m, num;
int h[N];
int dp[N][N];

void add(int u, int v, int w)
{
    e[++num].next = h[u];
    e[num].to = v;
    e[num].dis = w;
    h[u] = num;
}

void dfs(int x, int fat)
{
    for(int i = h[x]; i != 0; i = e[i].next)
        if(e[i].to != fat)
        {
            dp[e[i].to][1] = e[i].dis;
            dfs(e[i].to, x);
        }
    for(int i = h[x]; i != 0; i = e[i].next)
        if(e[i].to != fat)
        {
            int now = e[i].to;
            for(int j = m - 1; j >= 1; j--)
                for(int k = 0; k <= j; k++)
                    dp[x][j + 1] = max(dp[x][j + 1], dp[x][j + 1 - k] + dp[now][k]);
        }
}

int main()
{
    cin >> n >> m, m++;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0);
    cout << dp[1][m];
    return 0;
}