学步园

最简单的树形dp

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int n , m , e , a , b , val[205];
int head[205];
int dp[205][205];

struct T{
    int u , v , next;
}edge[41000];

void addedge(int u , int v){
    edge[e].u = u;
    edge[e].v = v;
    edge[e].next = head[u];
    head[u] = e ++;
}

void init(){
    memset(dp , 0 , sizeof(dp));
    memset(head , -1 , sizeof(head));
    e = 0;
}

void dfs(int u){
    dp[u][0] = 0;
    dp[u][1] = val[u];
    for(int i = head[u] ; i != -1 ; i = edge[i].next){
        int v = edge[i].v;
        dfs(v);
        for(int j = m + 1 ; j >= 1 ; j --){
            for(int k = 1 ; k < j ; k ++){
                dp[u][j] = max(dp[u][j] , dp[u][j - k] + dp[v][k]);
            }
        }
    }
    return ;
}


int main(){

    while(~scanf("%d%d" , &n , &m) && n || m){
        init();
        for(int i = 1 ; i <= n ; i ++){
            scanf("%d%d" , &a , &b);
            addedge(a , i);
            val[i] = b;
        }
        val[0] = 0;
        dfs(0);
        printf("%d\n" , dp[0][m+1]);
    }

    return 0;
}