编程介的小学生 2016-10-06 16:07 采纳率: 20.5%
浏览 1000
已采纳

Caves(树形DP)

It is said that the people of Menggol lived in caves. A tribe's caves were connected to each other with paths. The paths were so designed that there was one and only one path to each cave. So the caves and the paths formed a tree. There was a main cave, which connected the world outside. The Menggolian always carved a map of the tribe's caves on the wall of the main cave.
Scientists have just discovered Menggolian's tribe. What a heart-stirring discovery! They are eager to explore it. Since the terrain is very complex and dangerous, they decide to send out a robot.
The robot will be landed into the main cave, where he will begin his adventure. It doesn't have to return to the main cave, because the messages of his exploration will be sent immediately to the scientists while he is on the way.
A robot can only walk x meters before it runs out of energy. So the problem arises: given the map of the tribe's caves and a set of x , how many caves can be explored at most?
Input
There are multiple test cases in the input file. Each test case starts with a single number n(0$ \le$n$ \le$500) , which is the number of caves, followed by n - 1 lines describing the map. Each of the n - 1 lines contains three integers separated by blanks: i , j , and d(1$ \le$d$ \le$10000) . It means that the i -th cave's parent cave is the j -th cave and the distance is d meters. A parent cave of cave i is the first cave to enter on the path from i to the main cave. Caves are numbered from 0 to n - 1 . Then there is an integer q(1$ \le$q$ \le$1000) , which is the number of queries, followed by q lines. For one query, there is one integer x(0$ \le$x$ \le$5000000) , the maximum distance that the robot can travel. n = 0 indicates the end of input file.
Output
For each test case, output q lines in the format as indicated in the sample output, each line contains one integer, the maximum number of caves the robot is able to visit.
Sample Input
3
1 0 5
2 0 3
3
3
10
11
0
Sample Output
Case 1:
2
2
3

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-10-06 22:59
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致
  • ¥15 禅道二次开发编辑版本,上传不了发行包