题目名称	818. 通往自由的钥匙
输入输出	`key.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	Makazeu 于2012-06-15加入
开放分组	全部用户
提交状态
分类标签	动态规划
	分享题解

通过：45，提交：127，通过率：35.43%
Ezoi_XY	100	0.003 s	0.22 MiB	Pascal
0	100	0.004 s	0.35 MiB	C++
葳棠殇	100	0.004 s	0.36 MiB	C++
Aglove	100	0.004 s	0.40 MiB	C++
zys	100	0.004 s	0.52 MiB	C++
Herian	100	0.004 s	1.54 MiB	C++
Makazeu	100	0.005 s	0.36 MiB	C++
HouJikan	100	0.005 s	0.36 MiB	C++
落尘	100	0.005 s	0.36 MiB	C++
assassain	100	0.005 s	0.37 MiB	C++

关于通往自由的钥匙的近10条评论(全部评论)
手贱写了个初始化就跪了QAQ devil 2015-09-30 22:09 5楼
forever 2015-08-03 06:35 4楼
不是01背包加树归吗，怎么不对 .CPP 2015-06-15 16:46 3楼
一個人的雨 2015-06-15 15:59 2楼
写到要吐尼玛= =边界上各种不会处理 HouJikan 2014-09-06 14:10 1楼

818. 通往自由的钥匙

★☆ 输入文件：key.in 输出文件：key.out 简单对比
时间限制：1 s 内存限制：128 MiB

描述

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

输入

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

输出

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

样例输入

样例输出

提示

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