P13526 [KOI 2025 #2] 庆典

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

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$ 号城市举办庆典时的最大单日通行费收入。

### 限制条件 * 所有给定的数都是整数。 * $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 分) 无额外限制条件。