随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 202;
int n,m;
int val[maxn];
vector<int> G[maxn];
int dp[maxn][maxn];
bool vis[maxn];
void dfs(int u) {
    vis[u] = 1;
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i];
        if(vis[v]) continue;
        dfs(v);
        for(int j=m;j>=0;j--)
            for(int k=1;k<=j;k++) {
                dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]);   
            }   
    }   
    for(int i=m+1;i>=1;i--)
        dp[u][i] = dp[u][i-1] + val[u];
    dp[u][0] = 0;
}
int main() {
    while(~scanf("%d%d",&n,&m) && n + m) {
        for(int i=0;i<=n;i++) {
            G[i].clear();
            vis[i]=0;
            for(int j=0;j<=m+1;j++)
                dp[i][j] = 0;   
        }   
        val[0] = 0;
        int a,b;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&a,&b);
            G[a].push_back(i);
            val[i] = b;
        }
        dfs(0);
        int ans = dp[0][m+1];
        printf("%d\n",ans);
    }  
    return 0;
}