{"problem":{"name":"[ICPC 2020 Nanjing R] Monster Hunter","description":{"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$. Kotori would like to kill all th","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9634"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThere 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$.\n\n## Output\n\nFor 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!\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9634","tags":["动态规划 DP","2020","Special Judge","O2优化","树形 DP","ICPC","南京"],"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"]],"created_at":"2026-03-03 11:09:25"}}