众多照明方案

题目描述

有一棵以编号 $1$ 到 $N$ 的 $N$ 个顶点构成的有根树 $T$。根为顶点 $1$,顶点 $i$($2 \le i \le N$)的父节点为 $P_i$。

每个顶点具有两个非负整数值,称为美丽度和重量。顶点 $i$ 的美丽度和重量分别为 $B_i$ 和 $W_i$。

此外,每个顶点被涂成红色或蓝色。顶点 $i$ 的颜色用整数 $C_i$ 表示:若 $C_i = 0$,则顶点 $i$ 为红色;若 $C_i = 1$,则为蓝色。

对于顶点 $v$,设 $F(v)$ 为下面问题的答案。

设 $U$ 为以 $v$ 为根时 $T$ 的子树所构成的有根树。

你可以对 $U$ 进行零次或多次如下操作(操作不会改变未被删除顶点的美丽度、重量和颜色):

选择一个除根以外的顶点 $c$,设 $p$ 为 $c$ 的父节点。

对每一条父节点一侧端点为 $c$ 的边,进行如下操作:

设 $u$ 为该边除 $c$ 以外的另一个端点。删除这条边,并连接 $p$ 和 $u$ 形成一条新边(其中 $p$ 在父节点一侧)。

删除顶点 $c$,以及连接 $p$ 和 $c$ 的边。

若经过若干次操作后得到的 $U$ 满足以下所有条件,则称它是一棵好的有根树:

• $U$ 中每条边的两个端点颜色不同。
• 所有顶点的总重量不超过 $X$。

求在好的有根树中,顶点的美丽度之和的最大可能值。

求出所有 $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)$。

样例

4 10
1 2 2
2 1 0
4 2 1
6 8 0
7 4 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$。

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

11001
10110
10100
1000
10000

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

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

数据范围

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