【题目描述】VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第六题 博览会（exhibition）VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
某市正在举行一场大型博览会，博览会有 n 个展馆，每个展馆里有若干个展台。这 n 个展馆以及它们之间的道路可以看成一棵二叉树，博览会的出入口设在根节点——1 号展馆，小明将从这里出发乘坐电瓶车到各个展馆参观，并最终回到 1 号展馆出口。VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
由于路程差异，乘坐电瓶车往返不同展馆间的费用也有所区别。出发时，小明的乘车卡里余额为 k。他现在想知道，若全程都乘坐电瓶车，他最多能参观多少个展台？VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
说明：只要小明到达了某个展馆，就会参观该展馆内的所有展台，若多次参观同一个展台不重复计算。VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入数据】VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入共 n+2 行：VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 1 行为 2 个整数 n、k，用一个空格隔开，表示展馆个数和小明乘车卡初始余额。第 2 行为 n 个数，用一个空格隔开，表示 1 号至 n 号各展馆的展台数目。VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来 n 行，每行 4 个数，用一个空格隔开；第 i+2 行 4 个数分别表示展馆 i 左子节点展馆号、到左子节点展馆的费用、右子节点展馆号、到右子节点展馆的费用。如果子节点展馆号为 0 则表示没有对应的子节点展馆。VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出数据】VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出共 1 行，1 个整数，表示小明最多能参观的展台数量。VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输入】VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
10 20VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 8 5 1 10 5 9 9 3 5VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 1 3 2VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4 8 5 2VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
6 2 7 2VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
8 3 9 6VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0 0 10 2VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0 0 0 0VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0 0 0 0VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0 0 0 0VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0 0 0 0VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0 0 0 0VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输出】VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
39VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例说明】VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
根据样例数据，可以得到如下展馆二叉树示意图（每个圈内标示了展馆号及展台数）：VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
![【题目描述】 第六题 博览会（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 个整数，表示小明最多能参观的展台数量。 【样例输入】 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 【样例输出】 39 【样例说明】 根据样例数据，可以得到如下展馆二叉树示意图（每个圈内标示了展馆号及展台数）： 由图可知，小明沿红色箭号路径，到 1、2、5、3、6、7 这六个展馆参观并返回，往返乘车费用为 18，参观展台数为 39，为能够实现的最大值。 【数据范围】 对于 40%的数据：n≤10；k≤20； 对于 100%的数据：n≤50；k≤100；所有展馆的展台总数不超过 10^5。]( "【题目描述】 第六题 博览会（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 个整数，表示小明最多能参观的展台数量。 【样例输入】 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 【样例输出】 39 【样例说明】 根据样例数据，可以得到如下展馆二叉树示意图（每个圈内标示了展馆号及展台数）： 由图可知，小明沿红色箭号路径，到 1、2、5、3、6、7 这六个展馆参观并返回，往返乘车费用为 18，参观展台数为 39，为能够实现的最大值。 【数据范围】 对于 40%的数据：n≤10；k≤20； 对于 100%的数据：n≤50；k≤100；所有展馆的展台总数不超过 10^5。")
VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
由图可知，小明沿红色箭号路径，到 1、2、5、3、6、7 这六个展馆参观并返回，往返乘车费用为 18，参观展台数为 39，为能够实现的最大值。VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【数据范围】VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 40%的数据：n≤10；k≤20；VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 100%的数据：n≤50；k≤100；所有展馆的展台总数不超过 10^5。VrC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
