[CTSC1997]选课

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int n,m;
 6 
 7 int head[1010],nxt[1010],to[1010];
 8 int dp[1010][1010];
 9 //根节点为i，耗费空间为j 
10 //把背包融入树 
11 int _;
12 void add(int x,int y)
13 {
14     _++;
15     to[_]=y;
16     nxt[_]=head[x];
17     head[x]=_;
18     
19     return ;
20 }
21 
22 void makedp(int x)
23 {
24     for(int i=head[x];i;i=nxt[i])
25     {
26         int y=to[i];
27         makedp(y);//在处理x前，必然要处理他自己的儿子 
28         for(int j=m+1;j>0;j--)
29         {//来个背包 
30             for(int k=0;k<j;k++)
31             {//自身为子树，来j个
32             //max（自身，儿子节点+另外一些也选满） 
33             dp[x][j]=max(dp[x][j],dp[y][k]+dp[x][j-k]);    
34                 
35             }
36             
37             
38         }
39         
40     }
41 
42     return ;
43 }
44 
45 
46 
47 int main()
48 {
49     cin>>n>>m;    
50     for(int i=1;i<=n;i++)
51     {
52         int q;
53         cin>>q;//q为下面的编号 
54         add(q,i);//连边 
55         cin>>dp[i][1];//自身的子树，只选一个 
56         //所以只有自己 
57         //cin>>q>>w;
58         
59     }
60     makedp(0);
61     //0为根，从根开始可以考虑到所有状态 
62     cout<<dp[0][m+1];
63         
64     return   0;
65 }