洛谷 P2014 选课 参考代码

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

typedef long long LL;
const int maxn = 300 + 100;
int n, m, k;
int s[maxn];
vector<int> G[maxn];
int dp[maxn][maxn];

void dfs(int root) {
    for (int pos : G[root]) {
        dfs(pos);
    }
    for (int i = m; i >= 1; --i) {
        dp[root][i] = s[root];
    }
    for (int pos : G[root]) {
        for (int i = m; i >= 1; --i) {
            for (int j = 1; j < i; ++j) {
                dp[root][i] = max(dp[root][i], dp[root][i - j] + dp[pos][j]);
            }
        }
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    cin >> n >> m;
    ++m;
    for (int i = 1; i <= n; ++i) {
        cin >> k >> s[i];
        G[k].push_back(i);
    }
    dfs(0);
    cout << dp[0][m] << endl;

    return 0;
}