有树形依赖的背包

原理

见《进阶指南》第291页。

模板题

AcWing-10-有依赖的背包问题

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
struct edge {
    int to, next;
};
edge e[N];
int idx, head[N];
struct node {
    int v, w;
};
int n, m, root;
node a[N];
int f[N][N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur) {
    for (int j = a[cur].v; j <= m; ++ j) f[cur][j] = a[cur].w;
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        dfs(to);
        for (int j = m; j >= a[cur].v; -- j)
            for (int k = 0; k <= j - a[cur].v; ++ k)
                f[cur][j] = max(f[cur][j], f[cur][j - k] + f[to][k]);
    }
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1, p; i <= n; ++ i) {
        cin >> a[i].v >> a[i].w >> p;
        if (p == -1) {
            root = i;
        } else {
            add_edge(p, i);
        }
    }
    dfs(root);
    cout << f[root][m] << endl;
    return 0;
}