{"raw_statement":[{"iden":"statement","content":"There is a rooted tree with $n$ vertices and the root vertex is $1$. In each vertex, there is a monster. The hit points of the monster in the $i$-th vertex is $hp_i$.\n\nKotori would like to kill all the monsters. The monster in the $i$-th vertex could be killed if the monster in the direct parent of the $i$-th vertex has been killed. The power needed to kill the $i$-th monster is the sum of $hp_i$ and the hit points of all other living monsters who lives in a vertex $j$ whose direct parent is $i$. Formally, the power equals to \n$$\nhp_i + \\sum_{\\begin{array}{c}\\text{the monster in vertex } j \\text{ is \\bf{alive}} \\\\ \\text{and } i \\text{ is the direct parent of } j \\end{array}} hp_j\n$$\n\nIn addition, Kotori can use some magic spells. If she uses one magic spell, she can kill any monster using $0$ power without any restriction. That is, she can choose a monster even if the monster in the direct parent is alive.\n\nFor each $m=0,1,2,\\cdots,n$, Kotori would like to know, respectively, the minimum total power needed to kill all the monsters if she can use $m$ magic spells."},{"iden":"input","content":"There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($2 \\le n \\le 2 \\times 10^3$), indicating the number of vertices.\n\nThe second line contains $(n-1)$ integers $p_2,p_3,\\cdots,p_n$ ($1 \\le p_i < i$), where $p_i$ means the direct parent of vertex $i$.\n\nThe third line contains $n$ integers $hp_1,hp_2,\\cdots,hp_n$ ($1 \\le hp_i \\le 10^9$) indicating the hit points of each monster.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $2 \\times 10^3$."},{"iden":"output","content":"For each test case output one line containing $(n+1)$ integers $a_0, a_1, \\cdots, a_n$ separated by a space, where $a_m$ indicates the minimum total power needed to kill all the monsters if Kotori can use $m$ magic spells.\n\nPlease, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!"}],"translated_statement":null,"sample_group":[["3\n5\n1 2 3 4\n1 2 3 4 5\n9\n1 2 3 4 3 4 6 6\n8 4 9 4 4 5 2 4 1\n12\n1 2 2 4 5 3 4 3 8 10 11\n9 1 3 5 10 10 7 3 7 9 4 9","29 16 9 4 1 0\n74 47 35 25 15 11 7 3 1 0\n145 115 93 73 55 42 32 22 14 8 4 1 0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}