题目链接:https://www.luogu.org/problemnew/show/P2014

题解:用类似于分组背包的思想,不妨设f[i][j]f[i][j]为以ii为根的子树在选了jj个点的情况下的最大值那么f[i][j]f[i][j]只能由儿子来转移,那么就类似于多组背包的思想。

$i$的背包大小最多为$m$,有$son[i]$组物品,每组物品有$son[j]$个数量,对于每组而言只能选一个或者不选,体积为$j$ 那么 多重背包要如何实现呢? 参照《背包九讲》
```c++
#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 305 + 5;
struct edge {
    int u,v,next;
}e[MAXN * 10];
int head[MAXN],cnt,vis[MAXN],val[MAXN],f[MAXN][MAXN];
int n,m;
void insert(int u, int v) {
    e[++cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt;
}
void dfs(int u) {
    vis[u] = 1;
    f[u][0] = 0;
    for(int i = head[u]; i ; i = e[i].next) {
        int v = e[i].v;
        if(!vis[v]) {
            vis[v] = 1;
            dfs(v);
            for(int w = m; w >= 0; w--) {
                for(int j = w; j >= 0; j--) {
                    if(w - j >= 0) {
                        f[u][w] = max(f[u][w], f[u][w - j] + f[v][j]);
                    }
                }
            }
        }
    }
    if(u != 0) {
        for(int w = m; w >= 1; w--)
            f[u][w] = f[u][w - 1] + val[u];
    }
    return;
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int k,s;
        cin >> k >> s;
        insert(i, k); insert(k, i);
        val[i] = s;
    }
    dfs(0);
    cout << f[0][m];
    return 0;
}
```