CF1872F Selling a Menagerie

你拥有一个由 $n$ 只动物组成的动物园，这些动物编号从 $1$ 到 $n$。然而，维持这个动物园的开销非常大，所以你决定将其出售！ 已知每只动物都只害怕另一只特定的动物。更准确地说，第 $i$ 只动物害怕第 $a_i$ 只动物（$a_i \neq i$）。此外，每只动物的售价也是已知的，第 $i$ 只动物的售价为 $c_i$。 你将按照某种固定顺序出售所有动物。形式化地说，你需要选择一个排列 $p_1, p_2, \ldots, p_n$，依次出售动物 $p_1$、$p_2$，直到最后出售动物 $p_n$。 当你出售第 $i$ 只动物时，有两种可能的情况： - 如果第 $a_i$ 只动物在第 $i$ 只动物之前已经被卖出，你将以 $c_i$ 的价格出售第 $i$ 只动物。 - 如果第 $a_i$ 只动物在第 $i$ 只动物之前尚未被卖出，你将以 $2 \cdot c_i$ 的价格出售第 $i$ 只动物。（令人惊讶的是，当前处于害怕状态的动物更值钱。） 你的任务是选择一种出售动物的顺序，使得总收益最大。 例如，若 $a = [3, 4, 4, 1, 3]$，$c = [3, 4, 5, 6, 7]$，你选择的排列为 $[4, 2, 5, 1, 3]$，则： - 首先出售第 $4$ 只动物。第 $a_4 = 1$ 只动物尚未被卖出，因此你获得 $2 \cdot c_4 = 12$ 的收益。 - 第二只出售第 $2$ 只动物。第 $a_2 = 4$ 只动物已被卖出，因此你获得 $c_2 = 4$ 的收益。 - 第三只出售第 $5$ 只动物。第 $a_5 = 3$ 只动物尚未被卖出，因此你获得 $2 \cdot c_5 = 14$ 的收益。 - 第四只出售第 $1$ 只动物。第 $a_1 = 3$ 只动物尚未被卖出，因此你获得 $2 \cdot c_1 = 6$ 的收益。 - 第五只出售第 $3$ 只动物。第 $a_3 = 4$ 只动物已被卖出，因此你获得 $c_3 = 5$ 的收益。 你总共获得的收益为 $12 + 4 + 14 + 6 + 5 = 41$。注意，这并不是该例子的最大可能收益。 $^\dagger$ 长度为 $n$ 的排列是一个由 $n$ 个 $1$ 到 $n$ 的不同整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中出现了 $4$）。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示动物的数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$，$a_i \neq i$），其中 $a_i$ 表示第 $i$ 只动物害怕的动物编号。 每个测试用例的第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$），表示每只动物的售价。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出 $t$ 行，每行包含对应测试用例的答案。每行输出 $n$ 个整数，表示排列 $p_1, p_2, \ldots, p_n$，即出售动物的顺序，使得总收益最大。如果有多种答案，输出任意一种均可。

由 ChatGPT 4.1 翻译