Input Format

The first line of the input includes two positive integers (S and F) where S is the price of a single ticket and F is the price of a family ticket. The remaining lines of the test case are either the name of a person going by him/herself, or of the form:

N₁ N₂ N₃... N_k

where N₁ is the ID of a parent, with N2... N_k being his/her children. ID ’s are non-negative integers less then 100,000. No parent will be taking more than 1000 of their children to the movies:-). ID ’s unique, the ID of a particular person will appear at most twice: once as a parent, and once as a child. There will be at least one person and at most 100,000 people.

Output Format

Write the minimal total cost of tickets.

Sample Input/Output

Задача 2. “Caves”

(Весенний турнир имени Мартовского Зайца. 2008. Старшая лига. D)

Input file: caves.in

Output file: caves.out

Time limit 1 second

Memory limit 64M byte

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 the set of x, how many caves can be explored at most?

Input

Input file starts with a single number n (1 ≤ n ≤ 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 ≤ d ≤ 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 ≤ q ≤ 1000), which is the number of queries, followed by q lines. For one query, there is one integer x (0 ≤ x ≤ 5000000), the maximum distance that the robot can travel.

Output

For each test case, output q lines, each line contains one integer, the maximum number of caves the robot is able to visit.

Sample Input/Output

Поиск по сайту: