分数: 675 点
问题陈述
有一棵有根的树 T 与 N 顶点编号 1 to N。根是顶点 1,以及顶点的父级 i (2 \leq i \leq N) is P_i.
每个顶点都有两个非负整数值,称为 美女
长度为 $$$m$$$(其中 $$$m \ge 2$$$)的数组 $$$b$$$ 的 和 重量。顶点之美与重量 i 是 B_i 和 W_i。
此外,每个顶点都被涂成红色或蓝色。顶点颜色 i 用整数表示 C_i:顶点 i 被漆成红色,如果 C_i = 0,如果 C_i = 1.
对于顶点 v,让 F(v) 是以下问题的答案。
让 U 是有根树,它是 T 植根于 v.
您可以对 U 零次或多次。 (这些操作不会影响未删除的顶点的美观、权重或颜色。)
- 选择一个顶点 c 除根之外。让 p 是以下的父级 c.
- 对于父边上的端点为 c,执行以下操作:
- 让 u 是除 c。删除边并连接 p 和 u 有了新的优势, p 在父方。
- 删除顶点 c,以及边缘连接 p 和 c.
有根树,可以通过以下方式获得 U 经过一些操作被称为 根深蒂固的好树 当满足以下所有条件时。
- 对于每条边 U,边的端点有不同的颜色。
- 顶点的总权重最多为 X.
找到一棵有根的树中顶点的最大可能的总美度。
查找所有 F(1), F(2), \dots, F(N).
约束
- 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 is 0 or 1.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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).
示例输入 1
4 10 1 2 2 2 1 0 4 2 1 6 8 0 7 4 1
示例输出 1
9 10 6 7
对于 v=1,选择 c=2 然后 c=3 变化 U 如图所示,使其成为一棵扎根良好的树。 这棵树的顶点的总美度是 2 + 7 = 9,是所有有根好树中最大的,所以 F(1) = 9.

对于 v=2,选择 c=4 变化 U 如图所示,使其成为一棵扎根良好的树。 这棵树的顶点的总美度是 4 + 6 = 10,是所有有根好树中最大的,所以 F(2) = 10.

示例输入 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
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