文理学院程序设计在线练习


探索洞穴

Time Limit: 10 Second(s)    Memory Limit: 32 MB

Total Submission(s): 9   Accepted Submission(s): 2
Problem Description

据说蒙戈尔人住在洞穴里,部落的洞穴通过路径相互连接。有一个主要的洞穴,连接着外面的世界,蒙戈尔人总是在主洞穴的墙壁上雕刻出部落洞穴的地图。这些路径的设计使得每个洞穴只有一条路径通往主洞穴,所以洞穴和路径形成了一棵树。

科学家们刚刚发现了蒙戈尔人的部落。多么令人振奋的发现!他们渴望探索它。由于地形非常复杂和危险,他们决定派出一个机器人。

机器人将降落在主洞穴中,在那里它将开始它的冒险。它不必返回主洞穴,因为他的探索信息在途中时会实时发送给科学家。

机器人在耗尽能量之前只能行走x米。所以问题来了:考虑部落洞穴地图和x,最多可以探索多少个洞穴?

Input

第一行包含一个整数t(1<=t<=10)表示有t个例子。
对于每个例子,第一行一个整数n(0<=n<=500),这是洞穴的数量。
接着是描述地图的n-1行。n-1行中的每一行包含由空格分隔的三个整数:i,j和d(1<=d<=10000)。代表着第i个洞穴的父洞穴是第j个洞穴,距离是d米。洞穴的编号从0到n-1。
然后有一个整数q(1<=q<=1000),这是查询的数量,后跟q行。对于每一个查询,有一个整数x(0<=x<=5000000),即机器人可以行进的最大距离。

Output

对于每个例子,输出q行,每行包含一个整数,即机器人能够访问的最大洞穴数。

Sample Input
1
3 
1 0 5 
2 0 3 
3
3
10 
11 
Sample Output
2 
2 
3
Source

2019元培院赛