AT_abc311_h.[ABC311Ex] Many Illumination Plans

给定一棵根节点为1的有根树 $T$，树中共有 $N$ 个节点，编号从 $1$ 到 $N$。对于每个顶点 $i$（$2 \leq i \leq N$），其父节点是 $P_i$。每个节点都有两个非负整数属性，分别称为美丽值和重量。节点 $i$ 的美丽值为 $B_i$，重量为 $W_i$。此外，节点被涂上红色或蓝色，其颜色用整数 $C_i$ 表示：当 $C_i=0$ 时，节点 $i$ 为红色；当 $C_i=1$ 时，为蓝色。

对于每一个节点 $v$，定义函数 $F(v)$ 表示以下问题的解：

从树 $T$ 中提取出以 $v$ 为根的子树，称之为 $U$。对 $U$ 可以进行若干次以下操作（操作不会改变未删除节点的属性）：

• 选择一个非根节点 $c$，设 $c$ 的父节点为 $p$。
• 对于所有与 $c$ 相连的边：
  • 假设边的另一端是 $u$，删除这条边，然后用一条以 $p$ 为父节点的新边连接 $p$ 和 $u$。
• 删除节点 $c$ 和边 $p,c$。

最终的 $U$ 满足以下条件即为好的有根树：

• $U$ 中相连节点的颜色不同。
• 所有节点的重量总和不超过 $X$。

找出在所有可能的好的有根树中，节点美丽值总和的最大值。

请输出每个节点 $v$ 对应的 $F(v)$，即 $F(1), F(2), \dots, F(N)$。

输入从标准输入读取，格式如下：

$N$ $X$ $P_2$ $P_3$ $\dots$ $P_N$ $B_1$ $W_1$ $C_1$ $B_2$ $W_2$ $C_2$ $\vdots$ $B_N$ $W_N$ $C_N$

输出 $N$ 行。每行输出对应节点 $i$ 的最大美丽值 $F(i)$。

数据范围

• $2 \leq N \leq 200$
• $0 \leq X \leq 50000$
• $1 \leq P_i \leq i - 1$
• $0 \leq B_i \leq 10^{15}$
• $0 \leq W_i \leq X$
• $C_i$ 为 $0$ 或 $1$
• 所有输入的值均为整数

示例解释

对于 $v=1$，可以首先选择 $c=2$，然后选择 $c=3$，这样经过操作后的 $U$ 是一个好的有根树。该树中节点的美丽值总和是 $2 + 7 = 9$，为所有可能的好的有根树中的最大值，因此 $F(1) = 9$。

对于 $v=2$，选择 $c=4$ 后，得到的 $U$ 也是一个好的有根树。此时美丽值总和为 $4 + 6 = 10$，因此 $F(2) = 10$。

本翻译由 AI 自动生成