Bessie is going on a ski trip with her friends. The mountain has N
waypoints (1≤N≤105) labeled 1,2,…,N in increasing order of altitude (waypoint 1
is the bottom of the mountain).
For each waypoint i>1, there is a ski run starting from waypoint i and ending at waypoint pi (1≤pi <i). This run has difficulty di(0≤di≤109 ) and enjoyment ei (0≤ei ≤109 ).
Each of Bessie's M friends (1≤M≤105) will do the following: They will pick some initial waypoint i to start at, and then follow the runs downward (to pi , then to ppi, and so forth) until they get to waypoint 1.
The enjoyment each friend gets is equal to the sum of the enjoyments of the runs they follow. Each friend also has a different skill level sj (0≤sj≤109 ) and courage level cj (0≤cj≤10), which limits them to selecting an initial waypoint that results in them taking at most cj runs with difficulty greater than sj.
For each friend, compute the maximum enjoyment they can get.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
Then for each i from 2 to N, a line follows containing three space-separated integers pi, di, and ei.
The next line contains M.
The next M lines each contain two space-separated integers sj and cj.
OUTPUT FORMAT (print output to the terminal / stdout):
Output M lines, with the answer for each friend on a separate line.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
SAMPLE INPUT:
4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 0
SAMPLE OUTPUT:
0
300
500
300
500
500
300
500
1.The first friend cannot start any waypoint other than 1, since any other waypoint would cause them to take at least one run with difficulty greater than 19. Their total enjoyment is 0.
2.The second friend can start at waypoint 4 and take runs down to waypoint 2 and then 1. Their total enjoyment is 100+200=300. They take one run with difficulty greater than 19.
3.The third friend can start at waypoint 3 and take runs down to waypoint 2
and then 1. Their total enjoyment is 300+200=500. They take two runs with difficulty greater than 19.
SCORING:
Inputs 2-4: N,M≤1000
Inputs 5-7: All cj=0
Inputs 8-17: No additional constraints.
Problem credits: Brandon Wang
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
