← 返回题目列表

Codeforces · 1872/F

F. 出售动物园

中文机器翻译题面 查看原题

你是一个动物园的主人,动物园里有 $$$n$$$ 只动物,编号从 $$$1$$$ 到 $$$n$$$。然而,维护动物园的费用相当昂贵,所以你决定卖掉它!

众所周知,每种动物都害怕另一种动物。更准确地说,动物 $$$i$$$ 害怕动物 $$$a_i$$$ ($$$a_i \neq i$$$)。此外,每只动物的成本是已知的,对于动物$$$i$$$,它等于$$$c_i$$$。

您将按固定顺序出售所有动物。正式来说,您需要选择一些排列$$$^\dagger$$$ $$$p_1, p_2, \ldots, p_n$$$,然后首先出售动物 $$$p_1$$$,然后出售动物 $$$p_2$$$,依此类推,最后出售动物 $$$p_n$$$。

当您出售动物 $$$i$$$ 时,有两种可能的结果:

- 如果动物 $$$a_i$$$ 在动物 $$$i$$$ 之前被出售,则出售动物 $$$i$$$ 会收到 $$$c_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$$$。请注意,$$$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$$$,表示以何种顺序出售动物以最大化利润。如果有多个可能的答案,则可以输出其中任何一个。

示例

输入 #1

8
3
2 3 2
6 6 1
8
2 1 4 3 6 5 8 7
1 2 1 2 2 1 2 1
5
2 1 1 1 1
9 8 1 1 1
2
2 1
1000000000 999999999
7
2 3 2 6 4 4 3
1 2 3 4 5 6 7
5
3 4 4 1 3
3 4 5 6 7
3
2 1 1
1 2 2
4
2 1 4 1
1 1 1 1

输出 #1

1 2 3
2 4 5 1 6 3 7 8
3 4 5 1 2
1 2
7 5 1 3 2 6 4
5 3 2 4 1
3 2 1
3 4 1 2