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

#8598
서브태스크

축제 1.5s 1024MB

문제

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

KOI 나라에는 N - 1개의 양방향 도로가 있으며, 2 ≤i ≤ N인 모든 i에 대해, i번 도시는 P_i번 도시와 양방향 도로로 연결되어 있다.

이 때, P_i <i 를 만족하며, i번 도시와 P_i번 도시를 잇는 도로의 일일 이용량은 W_i이다.

1번 도시(수도)에서 v번 도시를 잇는 단순 경로 위에 u번 도시가 있다면, 우리는 u번 도시가 v번 도시를 통제한다고 정의한다.

i번 도시의 관리 구역은, i번 도시가 통제하는 모든 도시의 집합으로 정의된다.

이에 따라, 1번 도시의 관리 구역은 모든 도시이며, 1≤ i ≤ N인 모든 i에 대해 i번 도시는 i번 도시의 관리 구역에 속한다.

KOI 나라의 도로망을 1번 도시를 루트로 한 트리 구조로 보았을 때, i번 도시의 관리 구역은 i번 도시의 서브트리와 일치한다.

KOI 나라의 각 도시에서 축제를 열려고 한다.

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

i번 도시에서 축제가 열린다면, 도로 중 일부를 선택하여 통행료를 걷을 수 있다.

일일 통행료 수익은 통행료를 걷는 도로들의 일일 이용량의 합이다.

단, 사람들의 불만을 줄이기 위해 선택하는 도로들은 다음 두 조건을 만족해야 한다:

  • KOI 나라의 임의의 두 도시를 잇는 단순 경로 위에는, 통행료를 걷는 도로가 K개 이하로 존재해야 한다.

  • 통행료를 걷는 도로가 잇는 두 도시가 모두 i번 도시의 관리 구역에 있어야 한다.

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


입력

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

이후 N -1개의 줄이 주어진다. i -1 (2 ≤ i ≤N)번째 줄에는 P_i와 W_i가 공백을 사이에 두고 주어진다.

[제약 조건]

  • 주어지는 모든 수는 정수이다.

  • 1≤K<N≤300\ 000

  • 2≤i≤ N인 모든 i에 대해 1 ≤ P_i <i

  • 2≤i ≤ N인 모든 i에 대해 0 ≤W_i ≤10^9


출력

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


부분문제

번호 점수 조건
#14점

N ≤ 3\ 000

#25점

세 개 이상의 도로가 연결된 도시는 최대 하나이다.

#311점

1번 도시와 N번 도시를 잇는 단순 경로 T에 대해, 모든 도시에서 최대 10개의 도로를 지나 T 위에 있는 도시로 이동할 수 있다.

#413점

N ≤ 100\ 000, 2 ≤ i ≤ N인 모든 i에 대해 W_i = 1

#58점

2 ≤ i ≤ N인 모든 i에 대해 W_i = 1

#617점

N ≤ 100\ 000, 2 ≤ i ≤ N인 모든 i에 대해 W_i는 i번 도시의 관리 구역에 속한 도시의 수와 같다.

#710점

2 ≤i ≤ N인 모든 i에 대해 W_i는 i번 도시의 관리 구역에 속한 도시의 수와 같다.

#815점

N ≤ 100\ 000

#917점

추가 제약 조건 없음.


예제 #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


출처

2025 KOI 2차 고4
로그인해야 코드를 작성할 수 있어요.