Knapsack problem with dependency

Example

Backpack and tree dp Combined version of

This topic is in the form of a tree , So we use the idea of recursion to consider

Because if you want to select a child node , You must select the root node , So recursion is more convenient

When the set is divided , First, divide the set according to the number of subtrees , Then divide it by volume

This is different from Jinming's budget plan , Jinming's budget plan is divided according to the plan , Because it has a small number of schemes , There are many schemes in this topic , Because there may be many nodes , So we use volume to divide , Like , The first subtree on the left , The volume used is 0 Under the circumstances , What is its greatest value , The volume is 1... Push back in turn , altogether m+1 Seed selection （ The largest volume is m）

In this way, it can be regarded as a group backpack , Think of each subtree as a group of items . Each item group has m+1 Items , The first 0 Items represent a volume of 0, The value is f[0], The fifth expression is , The volume is 5, The value is f[5], The first m Class represents that the volume is m, The value is f[m], In fact, each subtree is regarded as an item group , Only one item can be selected for each item group

dp How to optimize it ？ Is to use a certain number to represent a class

It is essentially a tree dp Framework , And then in the tree dp Under the framework of , We only need to consider each time , The relationship between the current root node and its child nodes , Just consider the relationship between the two layers , When considering the relationship between the two layers , We can find out , You can put every sub tree , Think of it as a group of items , This is the problem of grouping backpacks , It can be solved by grouping backpacks

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

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;
int f[N][N];// Deposited i Is the number of points ,j Is the volume used 

void add(int a, int b)
{
    
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    
    for (int i = h[u]; ~i; i = ne[i])   //  Recycle item group 
    {
    
        int son = e[i];
        dfs(e[i]);

        //  Pack in groups 
        for (int j = m - v[u]; j >= 0; j -- )  //  Circulation volume 
            for (int k = 0; k <= j; k ++ )  //  Circular decision 
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }
    // I feel I can think about it this way , Is assigned to this subtree j Volume , If j Greater than v[u], It means that something is selected in the subtree , therefore u Be sure to add 
    //  Put the object u add 
    for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;
}

int main()
{
    
    cin >> n >> m;

    memset(h, -1, sizeof h);
    int root;
    for (int i = 1; i <= n; i ++ )
    {
    
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else add(p, i);
    }

    dfs(root);

    cout << f[root][m] << endl;

    return 0;
}