Luo Gu p3177 tree coloring [deeply understand the cycle sequence of knapsack on tree]

Pre knowledge ：
AcWing 10 Backpack on the tree —— There is a knapsack problem of dependence

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n,m,root,dp[N][N];
int idx, ne[N], e[N], h[N], w[N], v[N];

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]){
    
        int son = e[i];
        dfs(son);
        for(int j = m - v[u]; j; j --)
            for(int k = 0; k <= j; ++ k)
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
    }    
    for(int i = m; i >= v[u]; -- i) dp[u][i] = dp[u][i - v[u]] + w[u];
    for(int i = 0; i < v[u]; ++ i)  dp[u][i] = 0;
}

int main(){
    
    cin >> n >> m;
    memset(h, -1, sizeof h);
    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 << dp[root][m];
    return 0;
}

This topic tips： Deform the statistical answer in the question , Become statistics The sum of the edge weight of each edge multiplied by the number of black dots on both sides and the edge weight multiplied by the number of white dots on both sides 【 It can be understood as ： Each pair of nodes with different colors on both sides of this edge , The statistical answer will pass this side once . So the total number of passes is the product of the number of black spots on both sides + The product of white dots on both sides 】, It turns into the knapsack problem on the tree .

About the problem of cycle order ：
1、 For the first layer of circulation j From big to small , Because the grouping backpack is omitted “ grouping ” One dimension of , So we can only flashback enumeration , This is the knapsack problem ;
2、 For the second layer, enumerate the number of black dots in the subtree k, It looks like Must enumerate in positive order . In an ordinary tree backpack , The order of enumeration at this level does not matter , because k = 0 Say no , It won't affect the answer ; There are no black spots in the operator tree , White dots will still affect the answer , therefore k = 0 It should be calculated first , So we need to The reason for positive enumeration is positive enumeration k It's from 0 At the beginning , And the state transition of this problem must first be k=0 Can be established only when the state of is transferred .
A better understanding explanation ：
“ But this problem is quite special , It's ours ｋ Can be equal to ０, This leads to a lack of confidence For every ｊ, the last one ｋ There must be an illegal transfer . Popular point , The last transfer is ：f[u][j]=max(f[u][j],f[u][j]+f[v][0]+val); This shift is bound to happen , And the source state we use f[u][j-k] because ｋ=0 Of reason , It has not met our original requirements “ The original state we need will not be here Update before ” 了 , because f[u][j] I don't know how many times it has been updated .”

So if you deal with it first k = 0 The situation of , In fact, it doesn't matter to enumerate in reverse order .

About why this problem needs to be initialized before making a tree knapsack -1 The problem of ：—— Remove illegal situations ：
We enumerate in the subtree of the current child node , Let's enumerate it. There are k A black spot , Then we need one that selects a total of j - k The state of a black dot , however If the total size of other subtrees is less than j - k Words , Then this state is obviously illegal , So we need to get rid of this situation .

General tree backpack , There is no such thing , Because the maximum volume is m, All that is missing must be used , So there is no need to remove illegal situations .

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 4010;

int idx, ne[N], e[N], h[N];
int n,k1,sz[N];
ll dp[N][N], w[N];

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

void dfs(int u, int fa){
    
    sz[u] = 1;
    dp[u][0] = dp[u][1] = 0;
    for(int i = h[u]; ~i; i = ne[i]){
    
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        sz[u] += sz[j];
    }
    for(int i = h[u]; ~i; i = ne[i]){
    
        int son = e[i];
        if(son == fa)   continue;
        for(int j = min(sz[u], k1); j >= 0; j --){
    
            for(int k = 0; k <= min(j, sz[son]); ++ k){
    
                if(dp[u][j - k] >= 0){
    
                    ll val = (ll)k * (k1 - k) * w[i] + (ll)(sz[son] - k) * (n - k1 - sz[son] + k) * w[i];
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k] + val);
                }
            }
        }
    }
}

int main(){
    
    cin >> n >> k1;
    memset(h, -1, sizeof h);
    memset(dp, -1, sizeof dp);
    for(int i = 1; i < n; ++ i){
    
        int a, b;   ll c;
        scanf("%d%d%lld",&a,&b,&c);
        add(a,b,c), add(b,a,c);
    }
    dfs(1,1);
    cout << dp[1][k1];
    return 0;
}