축제

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

KOI 나라에는 $N - 1$개의 양방향 도로가 있으며, $2 \le i \le N$인 모든 $i$에 대해, $i$번 도시는 $P_i$번 도시와 양방향 도로로 연결되어 있다. 이 때, $P_i < i$를 만족하며, $i$번 도시와 $P_i$번 도시를 잇는 도로의 일일 이용량은 $W_i$이다.

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

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

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

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

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

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

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

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

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

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