{"raw_statement":[{"iden":"problem statement","content":"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$.  \nEach 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.  \nAdditionally, 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$.\nFor vertex $v$, let $F(v)$ be the answer to the following problem.\n\n> Let $U$ be the rooted tree that is the subtree of $T$ rooted at $v$.  \n> 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.)\n> \n> *   Choose a vertex $c$ other than the root. Let $p$ be the parent of $c$.\n> *   For each edge whose endpoint on the parent side is $c$, do the following:\n>     *   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.\n> *   Delete the vertex $c$, and the edge connecting $p$ and $c$.\n> \n> 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.\n> \n> *   For every edge in $U$, the edge's endpoints have different colors.\n> *   The vertices have a total weight of at most $X$.\n> \n> Find the maximum possible total beauty of the vertices in a good rooted tree.\n\nFind all of $F(1), F(2), \\dots, F(N)$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 200$\n*   $0 \\leq X \\leq 50000$\n*   $1 \\leq P_i \\leq i - 1$\n*   $0 \\leq B_i \\leq 10^{15}$\n*   $0 \\leq W_i \\leq X$\n*   $C_i$ is $0$ or $1$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $X$\n$P_2$ $P_3$ $\\dots$ $P_N$\n$B_1$ $W_1$ $C_1$\n$B_2$ $W_2$ $C_2$\n$\\vdots$\n$B_N$ $W_N$ $C_N$"},{"iden":"sample input 1","content":"4 10\n1 2 2\n2 1 0\n4 2 1\n6 8 0\n7 4 1"},{"iden":"sample output 1","content":"9\n10\n6\n7\n\nFor $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$.\n![image](https://img.atcoder.jp/ghi/abc311h_e9c1607d075d1352a8dc9ec07fe3ef4991c33a9d56626c4ab3f337e0c9d8a429.jpg)\nFor $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$.\n![image](https://img.atcoder.jp/ghi/abc311h2_fbbe94f219fde3a66d7846819b00d81f125609dd63a1a6fe3028a114991129a3.jpg)"},{"iden":"sample input 2","content":"5 5\n1 2 2 3\n1 1 0\n10 1 1\n100 1 0\n1000 1 1\n10000 1 1"},{"iden":"sample output 2","content":"11001\n10110\n10100\n1000\n10000"},{"iden":"sample input 3","content":"20 100\n1 2 1 1 1 6 6 5 1 7 9 4 6 4 15 16 8 2 5\n887945036308847 12 0\n699398807312293 20 1\n501806283312516 17 0\n559755618233839 19 1\n253673279319163 10 1\n745815685342299 11 1\n251710263962529 15 0\n777195295276573 15 0\n408579800634972 17 0\n521840965162492 17 1\n730678137312837 18 1\n370007714721362 14 1\n474595536466754 17 0\n879365432938644 15 0\n291785577961862 20 0\n835878893889428 14 1\n503562238579284 10 0\n567569163005307 18 1\n368949585722534 15 0\n386435396601075 16 0"},{"iden":"sample output 3","content":"5329161389647368\n1570154676347343\n501806283312516\n2665577865131167\n1418696191276572\n3952333977838189\n982388401275366\n1344764458281880\n778587515356334\n521840965162492\n730678137312837\n370007714721362\n474595536466754\n879365432938644\n1631226710430574\n1339441132468712\n503562238579284\n567569163005307\n368949585722534\n386435396601075"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}