루미 알고리즘

#1124다이아축제축제

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

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

축제

원제: 축제

문제

KOI 나라는 NN개의 도시로 이루어져 있으며, 각 도시는 1,2,…,N1, 2, \ldots, N의 번호가 매겨져 있다. 11번 도시는 KOI 나라의 수도이다.

KOI 나라에는 N−1N - 1개의 양방향 도로가 있으며, 2≤i≤N2 \le i \le N인 모든 ii에 대해, ii번 도시는 PiP_i번 도시와 양방향 도로로 연결되어 있다. 이 때, Pi<iP_i < i를 만족하며, ii번 도시와 PiP_i번 도시를 잇는 도로의 일일 이용량은 WiW_i이다.

11번 도시(수도)에서 vv번 도시를 잇는 단순 경로 위에 uu번 도시가 있다면, 우리는 uu번 도시가 vv번 도시를 통제한다고 정의한다. ii번 도시의 관리 구역은, ii번 도시가 통제하는 모든 도시의 집합으로 정의된다. 이에 따라, 11번 도시의 관리 구역은 모든 도시이며, 1≤i≤N1 \le i \le N인 모든 ii에 대해 ii번 도시는 ii번 도시의 관리 구역에 속한다. KOI 나라의 도로망을 11번 도시를 루트로 한 트리 구조로 보았을 때, ii번 도시의 관리 구역은 ii번 도시의 서브트리와 일치한다.

KOI 나라의 각 도시에서 축제를 열려고 한다. 평소에는 모든 도로의 통행료가 무료이지만, 축제가 열릴 때에는 축제를 여는 비용을 충당하기 위해 일부 도로에서 통행료를 걷으려고 한다.

ii번 도시에서 축제가 열린다면, 도로 중 일부를 선택하여 통행료를 걷을 수 있다. 일일 통행료 수익은 통행료를 걷는 도로들의 일일 이용량의 합이다. 단, 사람들의 불만을 줄이기 위해 선택하는 도로들은 다음 두 조건을 만족해야 한다:

  • KOI 나라의 임의의 두 도시를 잇는 단순 경로 위에는, 통행료를 걷는 도로가 KK개 이하로 존재해야 한다.
  • 통행료를 걷는 도로가 잇는 두 도시가 모두 ii번 도시의 관리 구역에 있어야 한다.

1≤i≤N1 \le i \le N인 모든 ii에 대해, ii번 도시에서 축제가 열린다고 가정할 때 일일 통행료 수익의 최댓값을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤K<N≤300 0001 \le K < N \le 300\,000
  • 2≤i≤N2 \le i \le N인 모든 ii에 대해 1≤Pi<i1 \le P_i < i
  • 2≤i≤N2 \le i \le N인 모든 ii에 대해 0≤Wi≤1090 \le W_i \le 10^9

부분문제

  1. (4점) N≤3 000N \le 3\,000
  2. (5점) 세 개 이상의 도로가 연결된 도시는 최대 하나이다.
  3. (11점) 11번 도시와 NN번 도시를 잇는 단순 경로 TT에 대해, 모든 도시에서 최대 1010개의 도로를 지나 TT 위에 있는 도시로 이동할 수 있다.
  4. (13점) N≤100 000N \le 100\,000, 2≤i≤N2 \le i \le N인 모든 ii에 대해 Wi=1W_i = 1
  5. (8점) 2≤i≤N2 \le i \le N인 모든 ii에 대해 Wi=1W_i = 1
  6. (17점) N≤100 000N \le 100\,000, 2≤i≤N2 \le i \le N인 모든 ii에 대해 WiW_i는 ii번 도시의 관리 구역에 속한 도시의 수와 같다.
  7. (10점) 2≤i≤N2 \le i \le N인 모든 ii에 대해 WiW_i는 ii번 도시의 관리 구역에 속한 도시의 수와 같다.
  8. (15점) N≤100 000N \le 100\,000
  9. (17점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 NN와 KK가 공백을 사이에 두고 주어진다.

이후 N−1N - 1개의 줄이 주어진다. i−1i - 1(2≤i≤N2 \le i \le N)번째 줄에는 PiP_i와 WiW_i가 공백을 사이에 두고 주어진다.

출력 형식

총 NN개의 줄을 출력한다. ii(1≤i≤N1 \le i \le N)번째 줄에는 ii번 도시에서 축제가 열릴 때 일일 통행료 수익의 최댓값을 출력한다.

예제

예제 1

입력
7 2
1 5
1 5
2 2
2 2
3 2
3 2
출력
10
4
4
0
0
0
0

예제 2

입력
7 3
1 5
1 5
2 2
2 2
3 2
3 2
출력
14
4
4
0
0
0
0

예제 3

입력
7 3
1 5
1 5
2 3
2 3
3 3
3 3
출력
17
6
6
0
0
0
0

예제 4

입력
20 4
1 1
1 2
2 4
3 0
4 7
6 2
4 10
2 9
4 2
2 5
8 1
6 1
11 5
5 9
1 1
16 6
7 10
6 3
8 7
출력
78
60
9
41
9
16
10
8
0
0
5
0
0
0
0
6
0
0
0
0

자료

출처 표기

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