[ NHOI ] 2018 博览会 exhibition - 题目

某市正在举行一场大型博览会，博览会有n个展馆，每个展馆里有若干个展台。这n个展馆以及它们之间的道路可以看成一棵二叉树，博览会的出入口设在根节点——1号展馆，小明将从这里出发乘坐电瓶车到各个展馆参观，并最终回到1号展馆出口。

由于路程差异，乘坐电瓶车往返不同展馆间的费用也有所区别。出发时，小明的乘车卡里余额为k。他现在想知道，若全程都乘坐电瓶车，他最多能参观多少个展台？

说明：只要小明到达了某个展馆，就会参观该展馆内的所有展台，若多次参观同一个展台不重复计算。

输入共n+2行：

第1行为2个整数n、k，用一个空格隔开，表示展馆个数和小明乘车卡初始余额。

第2行为n个数，用一个空格隔开，表示1号至n号各展馆的展台数目。

接下来n行，每行4个数，用一个空格隔开；第i+2行4个数分别表示展馆i左子节点展馆号、到左子节点展馆的费用、右子节点展馆号、到右子节点展馆的费用。如果子节点展馆号为0则表示没有对应的子节点展馆。

输出共1行，1个整数，表示小明最多能参观的展台数量。

输入样例1

10 20
2 8 5 1 10 5 9 9 3 5
2 1 3 2
4 8 5 2
6 2 7 2
8 3 9 6
0 0 10 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

输出样例1

根据样例数据，可以得到如下展馆二叉树示意图（每个圈内标示了展馆号及展台数）：

由图可知，小明沿红色箭号路径，到1、2、5、3、6、7这六个展馆参观并返回，往返乘车费用为18，参观展台数为39，为能够实现的最大值。

对于40%的数据：n≤10；k≤20；

对于100%的数据：n≤50；k≤100；所有展馆的展台总数不超过$10^5$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$

蜗牛编程训练题库