选课（背包类树形dp）

即在树上做背包

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

 

struct my{

        int next;

        int v;

};

 

const int maxn=1000+10;

 

int adj[maxn],fa,n,m,dp[maxn][maxn];

my bian[maxn*2];

int score[maxn];

 

void myinsert( int u, int v){

      bian[++fa].v=v;

      bian[fa].next=adj[u];

      adj[u]=fa;

}

 

void dfs( int x){

      dp[x][0]=0;

      for ( int i=adj[x];i!=-1;i=bian[i].next){

         int v=bian[i].v;

             dfs(v);

             for ( int t=m;t>=0;t--){

                 for ( int j=t;j>=0;j--){

                         if (t-j>=0)

                     dp[x][t]=max(dp[x][t],dp[x][t-j]+dp[v][j]);

                 }

             }

      }

      if (x!=0){

         for ( int t=m;t>0;t--){

             dp[x][t]=dp[x][t-1]+score[x];

         }

      }

}

 

int main(){

     int v;

     memset (adj,-1, sizeof (adj));

     memset (bian,-1, sizeof (bian));

     scanf ( "%d%d" ,&n,&m);

     for ( int i=1;i<=n;i++){

         scanf ( "%d%d" ,&v,&score[i]);

         myinsert(v,i);

       //  myinsert(i,v);

     }

     dfs(0);

     printf ( "%d" ,dp[0][m]);

return 0;

}