Problems
Bessie is going on a ski trip with her friends. The mountain has N waypoints (1 <= N <= 10^5) 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 p_i (1 <= p_i < i). This run has difficulty d_i (0 <= d_i <= 10^9) and enjoyment e_i (0 <= e_i <= 10^9).
Each of Bessie's M friends (1 <= M <= 10^5) will do the following: They will pick some initial waypoint i to start at, and then follow the runs downward (to p_i, then to p_(p_i), and so on) until they reach 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 s_j (0 <= s_j <= 10^9) and courage level c_j (0 <= c_j <= 10), which limits them to selecting an initial waypoint that results in them taking at most c_j runs with difficulty greater than s_j.
For each friend, compute the maximum enjoyment they can get.
Input
The first line contains an integer N.
Then, for each waypoint i from 2 to N, a line follows containing three space-separated integers p_i, d_i, and e_i.
The next line contains an integer M.
The following M lines each contain two space-separated integers s_j and c_j.
Output
Output M lines, with the answer for each friend on a separate line: the maximum enjoyment that friend can obtain.
Example
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
0
300
500
300
500
500
300
500
The first friend cannot choose any starting waypoint other than 1 because any other starting point would require taking at least one run with difficulty greater than 19. Therefore, their total enjoyment is 0.
The second friend, with skill 19 and courage 1, can start at waypoint 4, taking runs to waypoint 2 and then 1, collecting an enjoyment of 100 + 200 = 300 while taking one run with difficulty greater than 19.
The third friend, with courage 2, can start at waypoint 3, achieving a total enjoyment of 300 + 200 = 500.
The remaining friends obtain their optimal enjoyment in a similar fashion.
You must sign in to write code.