루미 알고리즘

#1104다이아점수 경주점수 경주

KOI 2024 2차코딩고등부 4번출제 이종영이 문제가 어렵다면 — 배우는 순서 보기

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

점수 경주

원제: 점수 경주

문제

KOI 공원은 11번 지점부터 NN번 지점까지 NN개의 지점으로 구성되어 있으며, 두 지점을 잇는 N−1N - 1개의 도로가 있다. ii번째 도로는 UiU_i번 지점과 ViV_i번 지점을 이으며, 점수 WiW_i를 가진다(1≤i≤N−11 \le i \le N - 1).

KOI 공원에서는 어떤 두 지점이든 도로를 따라 서로 이동할 수 있다. 즉, KOI 공원은 트리 구조를 이룬다.

KOI 공원에서 점수 경주를 하려고 한다. 점수 경주는 다음과 같이 이루어진다.

  • 총 N−1N - 1명의 참가자가 시작 지점에서 출발해, 각자 시작 지점을 제외한 서로 다른 N−1N - 1개의 지점으로 단순 경로를 따라 이동한다.
  • 각 참가자는 처음에 00점의 점수를 가지고 있다.
  • 각 도로에 대해, 해당 도로를 지나면 그 도로의 점수만큼 점수를 받게 된다.
  • 참가자들은 어떤 지점에서든 자신의 점수를 00점으로 만들 수 있다. 자신의 목표 지점으로 도착한 후에도 가능하다.

어떤 참가자의 최종 점수를 최대화하는 방법의 하나로는 어떤 지점에서 점수가 00점 미만이 될 때마다 00점으로 바꾸는 방법이 있다. 이를 최적 전략이라고 하자. 참가자들은 모두 최적 전략을 따르기로 하였다.

ii번 지점에 대해, 해당 지점이 시작 지점일 때 최적 전략을 따랐을 때 참가자들의 최종 점수의 총합을 SiS_i라고 하자. 또한 그때 참가자들이 자신의 점수를 00점으로 바꾼 횟수의 총합을 CiC_i라고 하자.

예를 들어, KOI 공원의 모습이 다음과 같을 때, 11번 지점이 시작 지점인 경우를 생각해 보자.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

최적 전략을 따를 때, 점수 경주의 과정은 다음과 같다.

  • 22번 지점이 목표 지점인 참가자는 22번 지점으로 이동하며 −1-1점을 받게 된다. 이후 22번 지점에서 자신의 점수를 00점으로 만든다. 최종 점수는 00점이다.
  • 33번 지점이 목표 지점인 참가자는 33번 지점으로 이동하며 22점을 받게 된다. 최종 점수는 22점이다.
  • 44번 지점이 목표 지점인 참가자는 22번 지점으로 이동하며 −1-1점을 받는다. 이후 22번 지점에서 자신의 점수를 00점으로 만든다. 이후 44번 지점으로 이동하며 22점을 받게 된다. 최종 점수는 22점이다.
  • 55번 지점이 목표 지점인 참가자는 33번 지점으로 이동하며 22점을 받는다. 이후 55번 지점으로 이동하며 −3-3점을 받는다. 이후 55번 지점에서 자신의 점수를 00점으로 만든다. 최종 점수는 00점이다.
  • 66번 지점이 목표 지점인 참가자는 33번 지점으로 이동하며 22점을 받는다. 이후 66번 지점으로 이동하며 −1-1점을 받게 된다. 최종 점수는 11점이다.

따라서 S1=5S_1 = 5, C1=3C_1 = 3이다.

S1,⋯ ,SNS_1, \cdots, S_N 및 C1,⋯ ,CNC_1, \cdots, C_N을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤300 0002 \le N \le 300\,000
  • 1≤Ui,Vi≤N1 \le U_i, V_i \le N (1≤i≤N−1)(1 \le i \le N - 1)
  • −10 000 000≤Wi≤10 000 000-10\,000\,000 \le W_i \le 10\,000\,000 (1≤i≤N−1)(1 \le i \le N - 1)

부분문제

  1. (2점) N≤1 000N \le 1\,000
  2. (6점) 0≤Wi≤50 \le W_i \le 5 (1≤i≤N−1)(1 \le i \le N - 1)
  3. (20점) 0≤Wi≤50 \le W_i \le 5 또는 Wi≤−1 000 000W_i \le -1\,000\,000 (1≤i≤N−1)(1 \le i \le N - 1)
  4. (4점) Ui=1U_i = 1, Vi=i+1V_i = i + 1 (1≤i≤N−1)(1 \le i \le N - 1)
  5. (10점) Ui=iU_i = i, Vi=i+1V_i = i + 1 (1≤i≤N−1)(1 \le i \le N - 1)
  6. (16점) Ui=⌊i+12⌋U_i = \lfloor \frac{i+1}{2} \rfloor, Vi=i+1V_i = i + 1 (1≤i≤N−1)(1 \le i \le N - 1)
  7. (18점) 세 개 이상의 다른 지점과 도로로 연결된 지점은 최대 두 개이다.
  8. (24점) 추가 제약 조건 없음.

각 부분문제에 대해, S1,⋯ ,SNS_1, \cdots, S_N만을 구한 경우 해당 부분문제의 점수의 절반을 얻을 수 있다. 그 방법에 대해서는 출력 형식을 참고하라. S1,⋯ ,SNS_1, \cdots, S_N 및 C1,⋯ ,CNC_1, \cdots, C_N을 구한 경우, S1,⋯ ,SNS_1, \cdots, S_N이 정확해도 C1,⋯ ,CNC_1, \cdots, C_N이 정확하지 않다면 점수를 받을 수 없음에 유의하라.

입력 형식

첫 번째 줄에 NN이 주어진다.

이후 N−1N - 1개의 줄에 걸쳐 ii번째 줄에는 UiU_i, ViV_i, WiW_i가 공백으로 구분되어 주어진다.

출력 형식

S1,⋯ ,SNS_1, \cdots, S_N만을 구한 경우

  • 첫 번째 줄에 00을 출력한다.
  • 두 번째 줄에 S1,⋯ ,SNS_1, \cdots, S_N을 공백으로 구분하여 출력한다.

S1,⋯ ,SNS_1, \cdots, S_N 및 C1,⋯ ,CNC_1, \cdots, C_N을 구한 경우

  • 첫 번째 줄에 11을 출력한다.
  • 두 번째 줄에 S1,⋯ ,SNS_1, \cdots, S_N을 공백으로 구분하여 출력한다.
  • 세 번째 줄에 C1,⋯ ,CNC_1, \cdots, C_N을 공백으로 구분하여 출력한다.

예제

예제 1

입력
6
1 2 -1
1 3 2
2 4 2
3 5 -3
3 6 -1
출력
1
5 5 6 8 6 6
3 5 2 0 6 6

예제 2

입력
10
5 10 5
4 7 5
1 6 1
8 9 5
9 4 1
6 7 0
5 1 0
2 9 3
4 3 3
출력
1
51 75 71 47 51 47 47 91 51 91
0 0 0 0 0 0 0 0 0 0

예제 3

입력
10
8 1 -2
10 5 -2
10 6 1
3 8 3
10 8 3
4 6 4
9 8 -5
9 7 5
6 2 -4
출력
1
24 23 40 48 21 23 24 24 24 21
11 12 2 0 12 4 1 3 9 4

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 2차 대회 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.