레이팅 미적용베시는 친구들과 스키 여행을 간다. 산에는 고도가 증가하는 순서대로 \(1, 2, \ldots, N\)으로 번호가 붙은 \(N\)개의 지점 (\(1\leq N \leq 10^5\))이 있다 (지점 \(1\)이 산의 맨 아래이다).
각 지점 \(i > 1\)에 대해, 지점 \(i\)에서 출발하여 지점 \(p_i\) (\(1\le p_i
베시의 \(M\)명의 친구들 (\(1\leq M \leq 10^5\))은 각각 다음과 같이 행동한다. 시작할 초기 지점 \(i\)를 하나 고른 뒤, 지점 \(1\)에 도착할 때까지 코스를 따라 아래로 내려간다 (\(p_i\)로, 그 다음 \(p_{p_i}\)로, 그리고 계속).
각 친구가 얻는 즐거움은 그들이 따라간 코스들의 즐거움의 합과 같다. 또한 각 친구는 서로 다른 실력 수준 \(s_j\) (\(0 \leq s_j \leq 10^9\))와 용기 수준 \(c_j\) (\(0 \leq c_j \leq 10\))를 가지며, 이 때문에 난이도가 \(s_j\)보다 큰 코스를 최대 \(c_j\)개까지만 타게 되는 초기 지점만 선택할 수 있다.
각 친구에 대해 얻을 수 있는 최대 즐거움을 계산하라.
Problem credits: Brandon Wang
SCORING
- 입력 2-4: \(N, M\le 1000\)
- 입력 5-7: 모든 \(c_j=0\)
- 입력 8-17: 추가 제약 없음.
Problem credits: Brandon Wang
첫째 줄에 \(N\)이 주어진다.
그 다음 각 \(i\) (\(2\)부터 \(N\)까지)에 대해, 공백으로 구분된 세 정수 \(p_i\), \(d_i\), \(e_i\)가 한 줄에 주어진다.
다음 줄에 \(M\)이 주어진다.
다음 \(M\)개의 줄에 각각 공백으로 구분된 두 정수 \(s_j\)와 \(c_j\)가 주어진다.
\(M\)개의 줄을 출력하며, 각 친구에 대한 답을 한 줄에 하나씩 출력한다.
이 문제에 등장하는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수 있음에 유의하라.
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 00
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\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > US Open > Silver