Luogu P2014 Code

P2014

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

vector<vector<int> > graph;
vector<int> cost;
int n,m;

int f[2005][2005];

int dfs(int node)
{
    int sum=0;
    f[node][1]=cost[node];
    for(vector<int>::iterator i=graph[node].begin();i!=graph[node].end();i++){
        int cnt=dfs(*i);
        sum+=cnt;
        for(int j=m+1;j>=1;j--)
            for(int k=sum;k>=0;k--){
                if(j<k+1) continue;
                f[node][j]=max(f[node][j],f[*i][k]+f[node][j-k]);
            }
    }
    sum++;
    return sum;
}

int main()
{
    scanf("%d%d",&n,&m);
    graph.resize(n+1);cost.resize(n+1);
    for(int i=1;i<=n;i++){
        int father;
        scanf("%d%d",&father,&cost[i]);
        graph[father].push_back(i);
    }
    dfs(0);
    printf("%d\n",f[0][m+1]);
    return 0;
}

转载自本人Luogu Blog的这篇文章