随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 150050;
int opt[505],n,K,root,w[maxn];
vector<int> g[maxn];
void dfs(int u,int *best) {
    int sz = g[u].size();
    int cur[505];
    for(int i=0;i<=K;i++) cur[i]=best[i];
    for(int i=0;i<sz;i++) {
        int v =  g[u][i];
        dfs(v,cur);   
    }   
    best[0] = 0;
    for(int i=K;i>0;i--) {
        best[i] = cur[i];
        if(best[i-1] >= 0)
            best[i] = max(best[i],best[i-1]+w[u]);   
    }
}
int main() {
    while(~scanf("%d%d",&n,&K)) {
        int p;
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=0;i<=K;i++) opt[i] = -inf;
        opt[0] = 0;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&p,&w[i]);
            if(p == 0) root = i;
            else g[p].push_back(i);   
        }   
        dfs(root,opt);
        if(opt[K] == -inf) puts("impossible");
        else printf("%d\n",opt[K]);
    }
    return 0;   
}