페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8417

Ski Slope 1s 1024MB

문제

Bessie는 친구들과 함께 스키 여행을 떠납니다. 산에는 고도가 증가하는 순서대로 번호가 매겨진 N개의 웨이포인트 (1\leq N \leq 10^5)가 있으며, 웨이포인트 1은 산 기슭(가장 낮은 지점)입니다.

1번을 제외한 각 웨이포인트 i>1에는 웨이포인트 i에서 시작하여 웨이포인트 p_i (1\le p_i < i)로 내려가는 스키 코스가 있습니다. 이 코스에는 난이도 d_i (0 \leq d_i \leq 10^9)와 즐거움 e_i (0 \leq e_i \leq 10^9)가 부여되어 있습니다.

Bessie의 M명의 친구들 (1\leq M \leq 10^5)은 각자 처음 시작할 웨이포인트 i를 선택한 후, 코스를 따라 (즉, p_i, 그 다음 p_{p_i}, …) 웨이포인트 1에 도달할 때까지 내려갑니다.

각 친구가 얻는 즐거움은 그들이 밟은 코스들의 즐거움의 총합입니다. 또한, 각 친구는 서로 다른 스킬 레벨 s_j (0 \leq s_j \leq 10^9)와 용기 레벨 c_j (0 \leq c_j \leq 10)를 가지며, 이는 친구들이 시작 웨이포인트를 선택할 때 “자신의 스킬 레벨 s_j보다 큰 난이도의 코스”를 최대 c_j번만 경험할 수 있도록 제한합니다.

각 친구별로, 조건을 만족하면서 얻을 수 있는 최대 즐거움을 구하세요.


입력

첫 번째 줄에 정수 N가 주어집니다.

이후, 웨이포인트 2부터 N까지 각 줄에 세 개의 정수 p_i, d_i, e_i가 공백으로 구분되어 주어집니다.

그 다음 줄에 정수 M가 주어집니다.

이후 M개의 줄 각각에 두 개의 정수 s_j와 c_j가 공백으로 구분되어 주어집니다.


출력

출력은 표준 출력에 M개의 줄로 구성되며, 각 친구에 대해 조건을 만족하며 얻을 수 있는 최대 즐거움을 한 줄에 하나씩 출력합니다.


예제 

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

첫 번째 친구는 스킬 레벨이 19이고 용기 0이므로, 난이도가 19보다 큰 코스를 한 번도 이용할 수 없습니다. 따라서 출발 웨이포인트로 1만 선택할 수 있어 즐거움은 0입니다.

두 번째 친구는 스킬이 19, 용기가 1이므로 최대 한 번 난이도가 19보다 큰 코스를 이용할 수 있습니다. 이 친구는 웨이포인트 4에서 시작하여 코스를 따라 내려가며 즐거움 100 + 200 = 300을 얻습니다.

세 번째 친구는 스킬이 19, 용기가 2이므로 최대 두 번의 어려운 코스를 이용할 수 있고, 웨이포인트 3에서 시작하면 즐거움이 300 + 200 = 500입니다.

나머지 친구들도 비슷한 최적의 선택을 통해 최대 즐거움을 얻습니다.


출처

USACO 2025 US Open Silver
로그인해야 코드를 작성할 수 있어요.