思路分析

一：本题属于背包类树形dp问题，同时还有依赖关系，这种题状态设计一般就是以谁为根有多大体积作为状态

C++ 代码

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

const int N = 310, M = N * 2;

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

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

void dfs(int u){
    dp[u][0] = 0;
    for(int i = h[u];~i;i = ne[i]){//物品组
        int k = v[i];
        dfs(k);
        for(int j = m-1;j >= 0;--j)//背包容量
            for(int t = 1;t <= j;++t)//决策组内的选择，下标从1开始可以参见前面的分组背包问题
                dp[u][j] = max(dp[u][j], dp[u][j-t] + dp[k][t]);
    }
    for(int j = m;j >= 0;--j) //选u本身也会有价值，加上选u的价值
        dp[u][j] = dp[u][j-1] + w[u];
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1;i <= n;++i){
        int fa;cin >> fa >> w[i]; 
        add(fa, i);
    }
    ++m;
    dfs(0);
    cout << dp[0][m] << endl;
    return 0;
}