题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

KOI 国由 $N$ 个城市组成，各城市分别编号为 $1, 2, \dots, N$。1 号城市是 KOI 国的首都。

KOI 国有 $N-1$ 条双向道路。对于所有满足 $2 \le i \le N$ 的 $i$，$i$ 号城市都与 $P_i$ 号城市通过一条双向道路相连。此时，满足 $P_i < i$，且连接 $i$ 号城市和 $P_i$ 号城市的道路的每日通行费是 $W_i$。

如果 $u$ 号城市位于从 1 号城市（首都）到 $v$ 号城市的简单路径上，我们定义为 $u$ 号城市管制 $v$ 号城市。$i$ 号城市的管辖区域被定义为 $i$ 号城市所管制的所有城市的集合。因此，1 号城市的管辖区域是所有城市，并且对于所有 $1 \le i \le N$，$i$ 号城市本身也属于其管辖区域。如果将 KOI 国的道路网看作一个以 1 号城市为根的树形结构，那么 $i$ 号城市的管辖区域就与以 $i$ 号城市为根的子树相对应。

KOI 国的各个城市计划举办庆典。平时所有道路的通行费都是免费的，但在庆典期间，为了分担举办庆典的费用，计划对部分道路征收通行费。

如果在 $i$ 号城市举办庆典，可以选择一部分道路来征收通行费。单日通行费收入是所有征收通行费的道路的每日通行费之和。为了减少民众的不满，选择的道路必须满足以下两个条件：

• 在 KOI 国内任意两个城市之间的简单路径上，征收通行费的道路数量必须不多于 $K$ 条。
• 征收通行费的道路，其两端点城市都必须位于 $i$ 号城市的管辖区域内。

请你编写一个程序，对于所有 $1 \le i \le N$ 的 $i$，分别计算当庆典在 $i$ 号城市举办时，能够获得的最大单日通行费收入。

输入格式

第一行给定 $N$ 和 $K$，以空格分隔。

之后 $N-1$ 行。第 $i-1(2 \le i \le N)$ 行给定 $P_i$ 和 $W_i$，以空格分隔。

输出格式

总共输出 $N$ 行。第 $i(1 \le i \le N)$ 行输出在 $i$ 号城市举办庆典时的最大单日通行费收入。

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

提示

限制条件

• 所有给定的数都是整数。
• $1 \le K < N \le 300\,000$
• 对于所有 $2 \le i \le N$，满足 $1 \le P_i < i$。
• 对于所有 $2 \le i \le N$，满足 $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$，满足 $W_i = 1$。
5. (8 分) 对于所有 $2 \le i \le N$，满足 $W_i = 1$。
6. (17 分) $N \le 100\,000$，且对于所有 $2 \le i \le N$，$W_i$ 的值等于 $i$ 号城市管辖区域内所含城市的数量。
7. (10 分) 对于所有 $2 \le i \le N$，$W_i$ 的值等于 $i$ 号城市管辖区域内所含城市的数量。
8. (15 分) $N \le 100\,000$。
9. (17 分) 无额外限制条件。