CF2254G Nightcrawler

Yousef 给了你一棵有根树 $^{\ast}$，该树共有 $n$ 个结点，根为结点 $1$。每个结点 $i$ 被赋予一个整数 $a_i$。 你需要将所有 $n$ 个结点恰好划分为 $k$ 个不相交的子集 $S_1, S_2, \dots, S_k$（也就是说，每个结点必须属于且仅属于这 $k$ 个集合之一），使得下述条件被满足： - 对于任意包含两个或以上结点的子集 $S_i$，对于 $S_i$ 中任意一对结点 $u, v$，必须有一个是另一个的祖先（即它们都在从根到某个叶子的同一条路径上）。 子集 $S_i$ 的得分定义为该集合中所有结点 $u$ 的 $a_u$ 的最大值。一次划分的得分是这 $k$ 个集合得分之和。换句话说，划分的总得分为 $\sum\limits_{i=1}^{k} \max\limits_{u \in S_i} a_u$。 对于每个 $k$，$1 \leq k \leq n$，请你计算满足条件的最大划分得分。如果无法将树恰好划分为 $k$ 个满足条件的集合，输出 $-1$。 $^{\ast}$ 一棵树是一个无环连通图。有根树是指树中一个点被指定为根。 $^{\dagger}$ 结点 $v$ 的祖先为从 $v$ 到根的简单路径上的所有结点（包括根，但不包括 $v$ 本身）。根结点没有祖先。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的组数。 每个测试用例第一行包含一个整数 $n$（$3 \leq n \leq 2 \times 10^5$）——表示结点个数。 每个测试用例第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——每个结点的取值。 每个测试用例第三行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \leq p_i < i$），其中 $p_i$ 是第 $i$ 个结点的父亲。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行 $n$ 个用空格隔开的整数。第 $k$ 个整数表示将树划分为 $k$ 个集合时的最大总得分。如果无法满足条件划分，输出 $-1$。

在第一个测试用例中： - 对于 $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$，每个结点为一个集合。得分 $5 + 10 + 15 + 20 = 50$。  第二组数据对应的树结构。 由 ChatGPT 5 翻译