루미 알고리즘

#1132골드산책로산책로

KOI 2026 1차코딩중등부 3번, 고등부 2번출제 윤교준이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

산책로

원제: 산책로

문제

KOI 산에는 11번부터 NN번까지 번호가 부여된 NN개의 쉼터가 있고, 그 쉼터들을 잇는 N−1N - 1개의 양방향 산책로가 있다.

ii (1≤i≤N1 \le i \le N)번 쉼터에 사람이 얼마나 많은지를 나타내는 밀집도는 양의 정수 AiA_i로 나타낼 수 있다.

jj (1≤j≤N−11 \le j \le N - 1)번째 산책로는 jj번 쉼터와 CjC_j번 쉼터를 이으며 (j+1≤Cj≤Nj + 1 \le C_j \le N), 그 길이는 LjL_j이다. 즉, 쉼터들은 산책로를 통해 연결된 트리 구조를 이룬다.

고독한 산책가 교준이는 서로 다른 두 쉼터를 골라, 두 쉼터 사이의 유일한 단순 경로를 따라 산책하려고 한다. 어떤 경로를 선택했을 때,

  • 경로에 포함된 산책로의 길이의 합을 SS,
  • 경로에 포함된 쉼터의 밀집도의 최댓값을 MM

이라고 하자. 교준이는 산책을 길게, 그러나 사람이 적은 곳에서 고독하게 즐기고 싶기 때문에, 이 경로의 만족도는 S−MS - M으로 정의된다.

교준이가 산책할 경로의 만족도를 최대화하기 위해서는 어떤 두 쉼터를 골라야 하는지 계산하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤300 0002 \le N \le 300\,000
  • 정수 ii (1≤i≤N1 \le i \le N)에 대하여 1≤Ai≤10181 \le A_i \le 10^{18}
  • 정수 jj (1≤j≤N−11 \le j \le N - 1)에 대하여 j+1≤Cj≤Nj + 1 \le C_j \le N이고 1≤Lj≤10121 \le L_j \le 10^{12}

부분문제

  1. (8점) N≤300N \le 300
  2. (12점) N≤7 500N \le 7\,500
  3. (11점) A1=A2=⋯=ANA_1 = A_2 = \cdots = A_N
  4. (15점) 정수 jj (1≤j≤N−11 \le j \le N - 1)에 대하여 Cj=j+1C_j = j + 1
  5. (17점) C1=C2=⋯=CN−1=NC_1 = C_2 = \cdots = C_{N-1} = N
  6. (36점) 집합 {A1,A2,⋯ ,AN}\{A_1, A_2, \cdots, A_N\}에 등장하는 서로 다른 정수의 개수는 2020 이하이다.
  7. (51점) 추가 제약 조건 없음.

입력 형식

첫 줄에 정수 NN이 주어진다.

그다음 줄에 NN개의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 N−1N - 1개의 정수 C1,C2,⋯ ,CN−1C_1, C_2, \cdots, C_{N-1}이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 N−1N - 1개의 정수 L1,L2,⋯ ,LN−1L_1, L_2, \cdots, L_{N-1}이 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄에 경로의 만족도가 최대가 되는 서로 다른 두 쉼터의 번호를 공백으로 구분하여 출력한다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.

예제

예제 1

입력
2
1 2
2
1
출력
1 2

11번 쉼터와 22번 쉼터 사이의 경로의 만족도는 −1-1로 최대이다.

예제 2

입력
4
6 10 20 1
2 4 4
3 21 15
출력
1 3

가능한 모든 경로의 만족도는 다음과 같다.

  • 경로 1−21 - 2의 만족도는 3−max⁡{6,10}=3−10=−73 - \max\{6, 10\} = 3 - 10 = -7.
  • 경로 1−2−4−31 - 2 - 4 - 3의 만족도는 (3+21+15)−max⁡{6,10,20,1}=39−20=19(3 + 21 + 15) - \max\{6, 10, 20, 1\} = 39 - 20 = 19.
  • 경로 1−2−41 - 2 - 4의 만족도는 (3+21)−max⁡{6,10,1}=24−10=14(3 + 21) - \max\{6, 10, 1\} = 24 - 10 = 14.
  • 경로 2−4−32 - 4 - 3의 만족도는 (21+15)−max⁡{10,20,1}=36−20=16(21 + 15) - \max\{10, 20, 1\} = 36 - 20 = 16.
  • 경로 2−42 - 4의 만족도는 21−max⁡{10,1}=21−10=1121 - \max\{10, 1\} = 21 - 10 = 11.
  • 경로 3−43 - 4의 만족도는 15−max⁡{20,1}=15−20=−515 - \max\{20, 1\} = 15 - 20 = -5.

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.