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 自动生成**

### 制約 - $ 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 $ - 入力される値はすべて整数 ### Sample Explanation 1 $ v=1 $ の場合、まず $ c=2 $ を選び、次に $ c=3 $ を選ぶと $ U $ は図のように変化して、操作後の $ U $ は良い根付き木になります。 この木に含まれる頂点の美しさの総和は $ 2\ +\ 7\ =\ 9 $ で、良い根付き木の中で最大です。よって $ F(1)\ =\ 9 $ です。 !\[image\](https://img.atcoder.jp/ghi/abc311h\_e9c1607d075d1352a8dc9ec07fe3ef4991c33a9d56626c4ab3f337e0c9d8a429.jpg) $ v=2 $ の場合、 $ c=4 $ を選ぶと $ U $ は図のように変化して、操作後の $ U $ は良い根付き木になります。 この木に含まれる頂点の美しさの総和は $ 4\ +\ 6\ =\ 10 $ で、良い根付き木の中で最大です。よって $ F(2)\ =\ 10 $ です。 !\[image2\](https://img.atcoder.jp/ghi/abc311h2\_fbbe94f219fde3a66d7846819b00d81f125609dd63a1a6fe3028a114991129a3.jpg)