luogu P2014 WA

// Problem: P2014 [CTSC1997] 选课
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2014
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;

vi g[512];
vi score;
int n, m;
vector<vector<int>> dp;

int dfs(int u, int fa, int c)
{
    if (dp[u][c] != INT_MIN / 2)
        return dp[u][c];
    dp[u][0] = 0;
    dp[u][1] = score[u];
    for (auto v : g[u]) {
        for (int i = c - 1; i > 0; --i) {
            int val = dfs(v, u, i);

            // dbg(v, u, i, val);
            for (int j = c; j > i; --j) {
                int old = dp[u][j];
                int opt = dp[u][j - i] + val;
                dp[u][j] = max(dp[u][j], dp[u][j - i] + val);
                if (old != opt && u == 0 && j == m + 1) {
                    fprintf(stderr, "old:%d,opt:%d[dp:%d,val:%d],u:0,v:%d,i:%d\n", old, opt, dp[u][j - i], val, v, i);
                }
            }
        }
    }

    return dp[u][c];
}

int main(int argc, char **argv)
{
    cin >> n >> m;
    score = vi(n + 1);
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k >> score[i];
        g[k].push_back(i);
    }
    dp = vv<int, INT_MIN / 2>(n + 1, m + 2);
    int ans = dfs(0, -1, m + 1);
    cout << ans << endl;
    return 0;
};