| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 80 | 45 | 37 | 57.812% |
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.
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 $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++).
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