silver_Ski_Slope (USACO US_Open_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: data structures, binary search, tree

Bessie is going on a ski trip with her friends. The mountain has $N$ waypoints
($1\leq N \leq 10^5$) labeled $1, 2, \ldots, 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\le p_i<i$).  This run has difficulty $d_i$
($0 \leq d_i \leq 10^9$) and enjoyment $e_i$ ($0 \leq e_i \leq 10^9$).
Each of Bessie's $M$ friends ($1\leq M \leq 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 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 $s_j$
($0 \leq s_j \leq 10^9$)  and courage level $c_j$ ($0 \leq c_j \leq 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 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 $p_i$, $d_i$, and $e_i$.
The next line contains $M$.
The next $M$ lines each contain two space-separated integers $s_j$ and $c_j$.
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
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$.
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$.
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\le 1000$
Inputs 5-7: All $c_j=0$
Inputs
8-17: No additional constraints.
Problem credits: Brandon Wang

Starter code:

Grader code:

Setup script:

Evaluation script: