103117: [Atcoder]ABC311 Ex - Many Illumination Plans

Problem Statement

There is a rooted tree $T$ with $N$ vertices numbered $1$ to $N$. The root is vertex $1$, and the parent of vertex $i$ $(2 \leq i \leq N)$ is $P_i$.
Each vertex has two non-negative integer values called beauty and weight. The beauty and weight of vertex $i$ are $B_i$ and $W_i$, respectively.
Additionally, each vertex is painted red or blue. The color of vertex $i$ is represented by an integer $C_i$: vertex $i$ is painted red if $C_i = 0$, and blue if $C_i = 1$.

For vertex $v$, let $F(v)$ be the answer to the following problem.

Let $U$ be the rooted tree that is the subtree of $T$ rooted at $v$.
You can perform the following sequence of operations on $U$ zero or more times. (The operations do not affect the beauties, weights, or colors of the vertices that are not being deleted.)

• Choose a vertex $c$ other than the root. Let $p$ be the parent of $c$.
• For each edge whose endpoint on the parent side is $c$, do the following:
  • Let $u$ be the endpoint of the edge other than $c$. Delete the edge and connect $p$ and $u$ with a new edge, with $p$ on the parent side.
• Delete the vertex $c$, and the edge connecting $p$ and $c$.

A rooted tree that can be obtained as $U$ after some operations is called a good rooted tree when all of the following conditions are satisfied.

• For every edge in $U$, the edge's endpoints have different colors.
• The vertices have a total weight of at most $X$.

Find the maximum possible total beauty of the vertices in a good rooted tree.

Find all of $F(1), F(2), \dots, F(N)$.

Constraints

• $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$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $N$ lines. The $i$-th line should contain $F(i)$.

Sample Input 1

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

Sample Output 1

9
10
6
7

For $v=1$, choosing $c=2$ and then $c=3$ changes $U$ as shown in the figure, making it a good rooted tree. The total beauty of the vertices in this tree is $2 + 7 = 9$, which is the maximum among all good rooted trees, so $F(1) = 9$.

For $v=2$, choosing $c=4$ changes $U$ as shown in the figure, making it a good rooted tree. The total beauty of the vertices in this tree is $4 + 6 = 10$, which is the maximum among all good rooted trees, so $F(2) = 10$.

Sample Input 2

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

Sample Output 2

11001
10110
10100
1000
10000

Sample Input 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

Sample Output 3

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

问题描述

有一个根节点为$1$的树$T$，包含$N$个节点，节点编号为$1$到$N$。节点$i$的父节点为$P_i$，$2 \leq i \leq N$。

每个节点有两种非负整数值，称为“美”和“重量”。节点$i$的美和重量分别为$B_i$和$W_i$。

此外，每个节点都被涂成红色或蓝色。节点$i$的颜色用整数$C_i$表示：如果$C_i = 0$，则节点$i$被涂成红色；如果$C_i = 1$，则节点$i$被涂成蓝色。

对于节点$v$，设$F(v)$为以下问题的答案。

让$U$为以节点$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$为$0$或$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
1418696191276