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

输入输出样例 #1

输入 #1

4 10
1 2 2
2 1 0
4 2 1
6 8 0
7 4 1

输出 #1

9
10
6
7

输入输出样例 #2

输入 #2

5 5
1 2 2 3
1 1 0
10 1 1
100 1 0
1000 1 1
10000 1 1

输出 #2

11001
10110
10100
1000
10000

输入输出样例 #3

输入 #3

20 100
1 2 1 1 1 6 6 5 1 7 9 4 6 4 15 16 8 2 5
887945036308847 12 0
699398807312293 20 1
501806283312516 17 0
559755618233839 19 1
253673279319163 10 1
745815685342299 11 1
251710263962529 15 0
777195295276573 15 0
408579800634972 17 0
521840965162492 17 1
730678137312837 18 1
370007714721362 14 1
474595536466754 17 0
879365432938644 15 0
291785577961862 20 0
835878893889428 14 1
503562238579284 10 0
567569163005307 18 1
368949585722534 15 0
386435396601075 16 0

输出 #3

5329161389647368
1570154676347343
501806283312516
2665577865131167
1418696191276572
3952333977838189
982388401275366
1344764458281880
778587515356334
521840965162492
730678137312837
370007714721362
474595536466754
879365432938644
1631226710430574
1339441132468712
503562238579284
567569163005307
368949585722534
386435396601075