60016 축제 Diamond IV

문제

KOI 나라는 N개 도시(1~N)로 이루어져 있으며, 1번 도시가 수도이다. N-1개의 양방향 도로가 있고, 각 도시 i(2 ≤ i ≤ N)는 P_i번 도시와 연결되어 있다 (P_i < i). 도로의 일일 이용량은 W_i이다.

1번에서 v번으로 가는 경로 위에 u번이 있으면, u가 v를 통제한다. i번 도시의 관리 구역은 i가 통제하는 모든 도시의 집합(= i의 서브트리)이다.

i번 도시에서 축제가 열릴 때, 일부 도로에 통행료를 걷는다:

1. 임의의 두 도시를 잇는 경로 위에 통행료 도로가 K개 이하로 존재
2. 통행료 도로의 양 끝 도시가 모두 i의 관리 구역에 속함

모든 i(1 ≤ i ≤ N)에 대해 i번 도시에서 축제가 열릴 때의 최대 일일 통행료 수익을 구하시오.

입력

첫째 줄에 N, K가 주어진다. (1 ≤ K < N ≤ 300,000)

다음 N-1줄(2 ≤ i ≤ N)에 P_i, W_i가 주어진다. (1 ≤ P_i < i, 0 ≤ W_i ≤ 10^9)

출력

N줄에 각 도시에서 축제 시 최대 수익을 출력한다.

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