#PU1520. USACO 2025 US Open Contest, Silver — Problem 3. Ski Slope

USACO 2025 US Open Contest, Silver — Problem 3. Ski Slope

USACO 2025 US Open Contest, Silver — Problem 3. Ski Slope

题目描述

Bessie is going on a ski trip with her friends. The mountain has NN waypoints (1≤N≤1051\leq N \leq 10^5) labeled 1,2,…,N1, 2, \ldots, N in increasing order of altitude (waypoint 11 is the bottom of the mountain). For each waypoint i>1i > 1, there is a ski run starting from waypoint ii and ending at waypoint pip_i (1≤pi<i1\le p_i<i). This run has difficulty did_i (0≤di≤1090 \leq d_i \leq 10^9) and enjoyment eie_i (0≤ei≤1090 \leq e_i \leq 10^9). Each of Bessie's MM friends (1≤M≤1051\leq M \leq 10^5) will do the following: They will pick some initial waypoint ii to start at, and then follow the runs downward (to pip_i, then to ppip_{p_i}, and so forth) until they get to waypoint 11. 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 sjs_j (0≤sj≤1090 \leq s_j \leq 10^9) and courage level cjc_j (0≤cj≤100 \leq c_j \leq 10), which limits them to selecting an initial waypoint that results in them taking at most cjc_j runs with difficulty greater than sjs_j. For each friend, compute the maximum enjoyment they can get.

输入格式

The first line contains NN. Then for each ii from 22 to NN, a line follows containing three space-separated integers pip_i, did_i, and eie_i. The next line contains MM. The next MM lines each contain two space-separated integers sjs_j and cjc_j.

输出格式

(见题面原文)

数据范围

Inputs 2-4: N,M≤1000N, M\le 1000 Inputs 5-7: All cj=0c_j=0 Inputs 8-17: No additional constraints. Problem credits: Brandon Wang

样例

样例 1

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 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$.

提示

use of 64-bit integer data types (e.g., a "long long" in C/C++).