34209번 - 축제 서브태스크

문제

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$

서브태스크

힌트