【题意】

通向自由的钥匙

Time Limit:10000MS  Memory Limit:65536K
Total Submit:96 Accepted:39 
Case Time Limit:1000MS

Description

通向自由的钥匙被放n个房间里，这n个房间由n-1条走廊连接。但是每个房间里都有特别的保护魔法，在它的作用下，我无法通过这个房间，也无法取得其中的钥匙。虽然我可以通过消耗能量来破坏房间里的魔法，但是我的能量是有限的。那么，如果我最先站在1号房间（1号房间的保护魔法依然是有效的，也就是，如果不耗费能量，我无法通过1号房间，也无法取得房间中的钥匙），如果我拥有的能量为P，我最多能取得多少钥匙？

Input

第一行包含两个非负整数，第一个为N，第二个为P。 
接下来n行，按1~n的顺序描述了每个房间。第i+1行包含两个非负整数cost和keys，分别为第i件房取消魔法需要耗费的能量和房间内钥匙的数量。 
接下来n-1行，每行两个非负整数x,y，表示x号房间和y号是连通的。

Output

一行一个整数，表示取得钥匙的最大值。

Sample Input

5 5
1 2
1 1
1 1
2 3
3 4
1 2
1 3
2 4
2 5

Sample Output

7

Hint

对于20%的测试数据，有n<=20 
对于30%的测试数据，有n<=30 
对于所有测试数据，有p,n<=100, cost <= 32767, keys<= 32767

【解题方法】


【AC 代码】

//
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,p,dp[105][105],r[105],l[105];
int key[105],cost[105];
bool mark[105],g[105][105];
void dfs1(int x){//多叉转二叉
    mark[x]=1;
    for(int i=1; i<=n; i++){
        if(!mark[i]&&g[x][i]){
            r[i] = l[x];
            l[x] = i;
            dfs1(i);
        }
    }
}
void dfs2(int x)
{
    int k;
    if(l[x]) dfs2(l[x]);
    if(r[x]) dfs2(r[x]);
    for(int y=0; y<=p; y++){
        dp[x][y]=dp[r[x]][y];
        for(k=0; k<=y-cost[x]; k++){}
            dp[x][y]=max(dp[x][y],key[x]+dp[l[x]][k]+dp[r[x]][y-k-cost[x]]);
    }
}
int main()
{
    cin>>n>>p;
    for(int i=1; i<=n; i++) cin>>cost[i]>>key[i];
    int u,v;
    for(int i=1; i<n; i++){
        cin>>u>>v;
        g[u][v]=g[v][u]=true;
    }
    dfs1(1);
    dfs2(1);
    cout<<dp[1][p]<<endl;
}