CF2254G Nightcrawler

Yousef has given you a rooted tree $ ^{\text{∗}} $ with $ n $ vertices, where the root is vertex $ 1 $ . Each vertex $ i $ is assigned an integer $ a_i $ . You must partition the set of all $ n $ vertices into exactly $ k $ disjoint subsets $ S_1, S_2, \dots, S_k $ (that is, each vertex must belong to exactly one of the $ k $ sets) such that the following condition is satisfied: - For any subset $ S_i $ containing two or more vertices, for every pair of vertices $ u, v \in S_i $ , one must be the ancestor $ ^{\text{†}} $ of the other (i.e., they must all lie on the same path extending from the root toward a leaf). The score of a subset $ S_i $ is defined as the maximum value $ a_u $ among all vertices $ u $ in that subset. The score of the partition is the sum of the scores of the $ k $ subsets. In other words, the score of the partition is equal to $ \sum\limits_{i=1}^{k} \max\limits_{u \in S_i} a_u $ . For every integer $ k $ from $ 1 $ to $ n $ , calculate the maximum possible score of a partition. If it is impossible to partition the tree into exactly $ k $ subsets that satisfy the condition, output $ -1 $ . $ ^{\text{∗}} $ A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root. $ ^{\text{†}} $ An ancestor of vertex $ v $ is any vertex on the simple path from $ v $ to the root, including the root, but not including $ v $ . The root has no ancestors.

The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains an integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of vertices. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the values of the vertices. The third line of each test case contains $ n-1 $ integers $ p_2, p_3, \dots, p_n $ ( $ 1 \le p_i \lt i $ ), where $ p_i $ is the parent of the $ i $ -th vertex. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single line containing $ n $ space-separated integers. The $ k $ -th integer should represent the maximum possible score for a partition of $ k $ subsets. If it is impossible to partition the tree into $ k $ subsets, output $ -1 $ for that value.

In the first test case: - For $ k = 1 $ , we would need all the vertices to be in the same set. However, for vertices $ 2 $ and $ 3 $ , neither of them is the ancestor of the other. Therefore, there is no valid partition. - For $ k = 2 $ , we can make $ S_1 = \{2\} $ , $ S_2 = \{1, 3\} $ . The score of this partition is $ \max\limits_{u \in S_1} a_u + \max\limits_{u \in S_2} a_u = 20 + 30 = 50 $ . It can be shown that this is the maximum score. - For $ k = 3 $ , we can make $ S_1 = \{1\} $ , $ S_2 = \{2\} $ , $ S_3 = \{3\} $ . The score of this partition is $ 10 + 20 + 30 = 60 $ .  The given tree in the first test case.In the second test case: - For $ k = 1 $ , we would need all the vertices to be in the same set. However, vertices $ 3 $ and $ 4 $ are not on the same root-to-leaf path, so this is impossible. - For $ k = 2 $ , we can make $ S_1 = \{3\} $ , $ S_2 = \{1,2,4\} $ . The score of this partition is $ \max\limits_{u \in S_1} a_u + \max\limits_{u \in S_2} a_u = 15 + 20 = 35 $ . It can be shown that this is the maximum score. - For $ k = 3 $ , we can make $ S_1 = \{3\} $ , $ S_2 = \{4\} $ , $ S_3 = \{1,2\} $ . The score of this partition is $ 15 + 20 + 10 = 45 $ . It can be shown that this is the maximum score. - For $ k = 4 $ , we can make $ S_1 = \{1\} $ , $ S_2 = \{2\} $ , $ S_3 = \{3\} $ , $ S_4 = \{4\} $ . The score of this partition is $ 5 + 10 + 15 + 20 = 50 $ .  The given tree in the second test case.