长乐 Day 10

#include <bits/stdc++.h>
using namespace std;
const int L = 1e3 + 10;
int n, m;
int dp[L][L];
int head[L], nxt[L];
int k[L];
int dfs(int x) {
    if (head[x] == -1)
        return 0;
    int s = 0;
    for (int i = head[x]; i != -1; i = nxt[i]) {
        int t = dfs(i);
        s += t + 1;
        for (int j = s; j >= 0; j--)
            for (int l = 0; l <= t; l++)
                if (j - l >= 1)
                    dp[x][j] = max(dp[x][j], dp[x][j - l - 1] + dp[i][l]);
    }
    return s;
}
void init() {
    memset(dp, 0, sizeof dp);
    memset(head, -1, sizeof head);
}
int main(void) {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= n; i++) {
        int q;
        scanf("%d%d", &q, &k[i]);
        nxt[i] = head[q];
        head[q] = i;
    }
    for (int i = 1; i <= n; i++) dp[i][0] = k[i];
    dp[0][0] = 0;
    dfs(0);
    printf("%d", dp[0][m]);
    return 0;
}