Starship Troopers

 1 #include"iostream"
 2 #include"vector"
 3 #include"cstring"
 4 using namespace std;
 5 const int size=105;
 6 int r,t;
 7 int cost[size],brain[size];
 8 int dp[size][size];
 9 vector<int> adj[size];
10 void dfs(int p,int pre);
11 int main()
12 {
13     while(cin>>r>>t)
14     {
15         if(r==-1&&t==-1)
16            break;
17         int bug,a,b,i;
18         for(i=0;i<r;i++)
19         {
20             cin>>bug>>brain[i];
21             cost[i]=(bug+19)/20;
22         }
23         for(i=0;i<r;i++)
24         {
25             adj[i].clear();
26         }
27         for(i=0;i<r-1;i++)
28         {
29             cin>>a>>b;
30             adj[a-1].push_back(b-1);
31             adj[b-1].push_back(a-1);
32         }
33         if(t==0)
34         {
35             cout<<‘0‘<<endl;
36             continue;
37         }
38         memset(dp,0,sizeof(dp));
39         dfs(0,-1);
40         cout<<dp[0][t]<<endl;
41     }
42     return 0;
43 }
44 void dfs(int p,int pre)
45 {
46     for(int i=cost[p];i<=t;i++)
47     {
48         dp[p][i]=brain[p];
49     }
50     int num=adj[p].size();
51     for(int i=0;i<num;i++)
52     {
53         int v=adj[p][i];
54         if(v==pre)
55           continue;
56         dfs(v,p);
57         for(int j=t;j>=cost[p];j--)
58           for(int k=1;k<=j-cost[p];k++)
59           {
60                 if(dp[p][j]<dp[p][j-k]+dp[v][k])
61                 {
62                      dp[p][j]=dp[p][j-k]+dp[v][k];
63                 }
64           }  
65     }
66 }