AT_abc311_h [ABC311Ex] Many Illumination Plans

[problemUrl]: https://atcoder.jp/contests/abc311/tasks/abc311_h 頂点に $ 1 $ から $ N $ までの番号がついた $ N $ 頂点の根付き木 $ T $ があります。根は頂点 $ 1 $ で、頂点 $ i $ $ (2\ \leq\ i\ \leq\ N) $ の親は $ P_i $ です。 各頂点には **美しさ**・**重さ** と呼ばれる 2 つの非負整数値がついています。頂点 $ i $ の美しさは $ B_i $ で重さは $ W_i $ です。 また、各頂点は赤か青で塗られています。頂点 $ i $ の色は整数 $ C_i $ で表されて、$ C_i\ =\ 0 $ のとき頂点 $ i $ は赤、$ C_i\ =\ 1 $ のとき青で塗られています。 頂点 $ v $ に対して、次の問題の答えを $ F(v) $ とおきます。 > $ T $ から $ v $ を根とする部分根付き木を取り出して出来る根付き木を $ U $ とします。 > あなたは $ U $ に対して以下の一連の操作を $ 0 $ 回以上好きなだけ行うことができます。(操作の前後で、削除されない頂点の美しさ・重さ・色はいずれも変化しません。) > > - 根以外の頂点 $ c $ を 1 つ選ぶ。$ c $ の親を $ p $ とする。 > - 頂点 $ c $ が親側の端点である辺全てに対して、次の操作を行う。 > - 辺の $ c $ でない端点を $ u $ とする。辺を削除して、代わりに $ 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) $ を出力せよ。

### 制約 - $ 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 $ - 入力される値はすべて整数 ### Sample Explanation 1 $ v=1 $ の場合、まず $ c=2 $ を選び、次に $ c=3 $ を選ぶと $ U $ は図のように変化して、操作後の $ U $ は良い根付き木になります。 この木に含まれる頂点の美しさの総和は $ 2\ +\ 7\ =\ 9 $ で、良い根付き木の中で最大です。よって $ F(1)\ =\ 9 $ です。 !\[image\](https://img.atcoder.jp/ghi/abc311h\_e9c1607d075d1352a8dc9ec07fe3ef4991c33a9d56626c4ab3f337e0c9d8a429.jpg) $ v=2 $ の場合、 $ c=4 $ を選ぶと $ U $ は図のように変化して、操作後の $ U $ は良い根付き木になります。 この木に含まれる頂点の美しさの総和は $ 4\ +\ 6\ =\ 10 $ で、良い根付き木の中で最大です。よって $ F(2)\ =\ 10 $ です。 !\[image2\](https://img.atcoder.jp/ghi/abc311h2\_fbbe94f219fde3a66d7846819b00d81f125609dd63a1a6fe3028a114991129a3.jpg)