National Olympiad in Informatics, China, 2014
This summer, NOI is celebrating her 30th birthday in city SZ. The OIers from cities across the nation will arrive in city SZ to participate in the celebration.
The cities in the nation form a tree rooted at city SZ. Each city is connected to its parent by a road. For the sake of simplicity, we have numbered the cities with unique integers from to . City SZ is numbered . Outside of city SZ itself, any city will have a parent denoted by , connected by a road of length .
Traveling from city to city SZ can be done in the following way: Select an ancestor of city , pay the ticket cost, and take the public transit to city . Then, pick ancestor of city , pay the ticket, and travel there. Repeat this process until city SZ is reached.
For any city , we place a limit on the distance of the public transit. For an ancestor of , if and only if the total distance of all the roads between and does not exceed , then it's possible to go straight to city from by buying one ticket. For each city , we can also provide two nonnegative integers and as the ticket price parameters. If we let the total distance of all roads from to equal , then the ticket cost to travel from to is .
OIers from all the cities wish to reach city SZ by themselves with the smallest total cost. Your task is to tell the OIers from each city the minimum possible cost they will need to pay to reach city SZ.
Input Specification
The first line of input will contain two nonnegative integers and ,
respectively representing the number of cities and the type of the test
case (explained below).
Lines 2 to of the input will each describe a city outside of city
SZ. Line will contain five nonnegative integers , ,
, , and , respectively representing the parent of
city , the length of the road to its parent, the ticket price
parameters, and the distance limit.
Note: the input will not contain city SZ which is numbered . Line 2 to
line will respectively represent the cities numbered from to .
Output Specification
Output lines, each line containing a single integer. Line
should indicate the minimum total ticket cost if an OIer wanted to
travel from city to city SZ.
Note again: the output should not include city SZ which is numbered .
Sample Input
7 3
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10
Sample Output
40
150
70
149
300
150
Explanation
Refer to the diagram below:
The paths to travel to SZ from every city is outlined as follows (where arrows represent a single, direct trip):
City 2: Only is possible, for a cost of .
City 3: Only is possible, for a cost of .
City 4: Since , one route is . If this is selected, then the cost will be . If instead the route is chosen, then the cost will be . Thus, the best route is .
City 5: Only is possible, for a cost of . is not valid – since , and city 5 to city 1's total distance is , 5 cannot directly reach 1.
City 6: If is selected, the cost will be . If is selected, the cost will be . Thus, the best route is .
City 7: Choose for a cost of . All other methods are suboptimal to this.
Constraints
All of the test cases satisfy , , , and . Also, the total distance between any city and city SZ will not exceed .
The input value represents the type of test case, :
When or , each of the input cities will have . That is, the cities will form a chain with SZ at one end.
When or , each of the input cities will have . That is, there will be no distance limit for traveling between cities – every city will be able to reach every one of its ancestors.
When , there will be no special characteristics for the test case.
The sizes of and for each test case are summarized as follows.
Test Case | ||
---|---|---|
1 | ||
2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 |
Warning
The input and output requires 64-bit integers. If your calculations require operating on two 64-bit integers, be careful of whether the result will overflow.
Problem translated to English by .
Comments