60016 축제 Diamond IV

문제

KOI 나라는 $N$개의 도시로 이루어져 있으며, 각 도시는 $1, 2, \dots , 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$가 공백을 사이에 두고 주어진다.

출력

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

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ K < N ≤ 300\, 000$
• $2 ≤ i ≤ N$인 모든 $i$에 대해 $1 ≤ P_i < i$
• $2 ≤ i ≤ N$인 모든 $i$에 대해 $0 ≤ W_i ≤ 10^9$

서브태스크

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

7 2
1 5
1 5
2 2
2 2
3 2
3 2

10
4
4
0
0
0
0

7 3
1 5
1 5
2 2
2 2
3 2
3 2

14
4
4
0
0
0
0

7 3
1 5
1 5
2 3
2 3
3 3
3 3

17
6
6
0
0
0
0

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