思路
每次都考虑以u为根的子树,f[u][i]表示以u为根节点,体积不超过i的最大价值
每次都必须把u选上,再考虑子树,把剩余体积分给各个子树,看各个子树利用这些剩余体积能拼凑出的最大价值是多少
这就转化为了分组背包问题
每棵子树利用体积v的产生的价值如果不为0,其也一定是选上了这个子树的根节点,依次递推保证了依赖关系
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int h[N], e[N], ne[N], idx;
int f[N][N];
int v[N], w[N];
int n, m, root;
void insert(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
void dfs(int u)
{
for(int i = v[u]; i <= m; i ++) f[u][i] = w[u];
for(int x = h[u]; ~x; x = ne[x]){
int y = e[x];
dfs(y);
for(int j = m; j >= v[u]; j --)//u和子树一共的体积
for(int k = 0; k <= j - v[u]; k ++)//分给子树的体积
f[u][j] = max(f[u][j], f[u][j - k] + f[y][k]);
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof(h));
for(int i = 1; i <= n; i ++){
int p;
scanf("%d%d%d", &v[i], &w[i], &p);
if(p == -1) root = i;
else insert(p, i);
}
dfs(root);
printf("%d\n", f[root][m]);
return 0;
}