← 返回题目列表

AtCoder · abc311_h

Ex. 多种照明方案

中文机器翻译题面 查看原题

分数: 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.

image

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

image2


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