축제

문제

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

KOI 나라에는 N − 1개의 양방향 도로가 있으며, 2 ≤ i ≤ N인 모든 $ii$에 대해, $ii$번 도시는 $P_{i}P\_i$번 도시와 양방향 도로로 연결되어 있다. 이 때, 를 만족하며, $ii$번 도시와 $P_{i}P\_i$번 도시를 잇는 도로의 일일 이용량은 $W_{i}W\_i$이다.

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

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

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

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

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

입력

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

이후 N − 1개의 줄이 주어진다. i − 1 (2 ≤ i ≤ N)번째 줄에는 $P_{i}P\_i$와 $W_{i}W\_i$가 공백을 사이에 두고 주어진다.

출력

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

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