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.

优素福给你一棵有 $n$ 个顶点的有根树$^{\text{∗}}$，其中根节点为顶点 $1$。每个顶点 $i$ 被赋予一个整数 $a_i$。

你需要将全部 $n$ 个顶点划分为恰好 $k$ 个互不相交的子集 $S_1, S_2, \dots, S_k$（即每个顶点必须且仅属于这 $k$ 个子集中的一个），使得满足以下条件：

• 对于任意包含两个或更多顶点的子集 $S_i$，对其中任意一对顶点 $u, v \in S_i$，$u$ 和 $v$ 中必有一个是另一个的祖先$^{\text{†}}$（即它们必须全部位于从根节点通向某个叶节点的同一条路径上）。

子集 $S_i$ 的得分定义为该子集中所有顶点 $u$ 的 $a_u$ 的最大值。划分的得分为这 $k$ 个子集得分之和。换言之，划分的得分等于 $\sum\limits_{i=1}^{k} \max\limits_{u \in S_i} a_u$。

对每个从 $1$ 到 $n$ 的整数 $k$，计算满足条件的划分所能达到的最大得分。若无法将该树恰好划分为 $k$ 个满足条件的子集，则输出 $-1$。

$^{\text{∗}}$树是无环的连通图。有根树是一棵指定某一顶点为根的树。

$^{\text{†}}$顶点 $v$ 的祖先是指从 $v$ 到根节点的简单路径上的任意顶点（包括根节点，但不包括 $v$ 自身）。根节点没有祖先。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）—— 顶点的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 各顶点的值。

每个测试用例的第三行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i \lt i$），其中 $p_i$ 表示第 $i$ 个顶点的父节点。

保证所有测试用例的 $n$ 之和不超过 $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.

对于每个测试用例，输出一行，包含 $n$ 个以空格分隔的整数。其中第 $k$ 个整数应表示将树划分为 $k$ 个子集时所能达到的最大得分。若无法将树划分为 $k$ 个子集，则对应位置输出 $-1$。

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.

在第一个测试用例中：

• 当 $k = 1$ 时，我们需要将所有顶点放入同一个集合中。然而，对于顶点 $2$ 和 $3$，它们互不为对方的祖先。因此，不存在合法的划分。
• 当 $k = 2$ 时，我们可以令 $S_1 = \{2\}$，$S_2 = \{1, 3\}$。该划分的得分为 $\max\limits_{u \in S_1} a_u + \max\limits_{u \in S_2} a_u = 20 + 30 = 50$。可以证明这是最大得分。
• 当 $k = 3$ 时，我们可以令 $S_1 = \{1\}$，$S_2 = \{2\}$，$S_3 = \{3\}$。该划分的得分为 $10 + 20 + 30 = 60$。

第一个测试用例中给出的树。

在第二个测试用例中：

• 当 $k = 1$ 时，我们需要将所有顶点放入同一个集合中。然而，顶点 $3$ 和 $4$ 不在同一条根到叶的路径上，因此这是不可能的。
• 当 $k = 2$ 时，我们可以令 $S_1 = \{3\}$，$S_2 = \{1,2,4\}$。该划分的得分为 $\max\limits_{u \in S_1} a_u + \max\limits_{u \in S_2} a_u = 15 + 20 = 35$。可以证明这是最大得分。
• 当 $k = 3$ 时，我们可以令 $S_1 = \{3\}$，$S_2 = \{4\}$，$S_3 = \{1,2\}$。该划分的得分为 $15 + 20 + 10 = 45$。可以证明这是最大得分。
• 当 $k = 4$ 时，我们可以令 $S_1 = \{1\}$，$S_2 = \{2\}$，$S_3 = \{3\}$，$S_4 = \{4\}$。该划分的得分为 $5 + 10 + 15 + 20 = 50$。

第二个测试用例中给出的树。