Selling a Menagerie
Contest: Codeforces Round 895 (Div. 3)
Difficulty rating: 1800
Tags: dfs and similar, dsu, graphs, implementation, math

You are the owner of a menagerie consisting of $$$n$$$ animals numbered from $$$1$$$ to $$$n$$$. However, maintaining the menagerie is quite expensive, so you have decided to sell it!

It is known that each animal is afraid of exactly one other animal. More precisely, animal $$$i$$$ is afraid of animal $$$a_i$$$ ($$$a_i \neq i$$$). Also, the cost of each animal is known, for animal $$$i$$$ it is equal to $$$c_i$$$.

You will sell all your animals in some fixed order. Formally, you will need to choose some permutation$$$^\dagger$$$ $$$p_1, p_2, \ldots, p_n$$$, and sell animal $$$p_1$$$ first, then animal $$$p_2$$$, and so on, selling animal $$$p_n$$$ last.

When you sell animal $$$i$$$, there are two possible outcomes:

- If animal $$$a_i$$$ was sold before animal $$$i$$$, you receive $$$c_i$$$ money for selling animal $$$i$$$.
- If animal $$$a_i$$$ was not sold before animal $$$i$$$, you receive $$$2 \cdot c_i$$$ money for selling animal $$$i$$$. (Surprisingly, animals that are currently afraid are more valuable).

Your task is to choose the order of selling the animals in order to maximize the total profit.

For example, if $$$a = [3, 4, 4, 1, 3]$$$, $$$c = [3, 4, 5, 6, 7]$$$, and the permutation you choose is $$$[4, 2, 5, 1, 3]$$$, then:

- The first animal to be sold is animal $$$4$$$. Animal $$$a_4 = 1$$$ was not sold before, so you receive $$$2 \cdot c_4 = 12$$$ money for selling it.
- The second animal to be sold is animal $$$2$$$. Animal $$$a_2 = 4$$$ was sold before, so you receive $$$c_2 = 4$$$ money for selling it.
- The third animal to be sold is animal $$$5$$$. Animal $$$a_5 = 3$$$ was not sold before, so you receive $$$2 \cdot c_5 = 14$$$ money for selling it.
- The fourth animal to be sold is animal $$$1$$$. Animal $$$a_1 = 3$$$ was not sold before, so you receive $$$2 \cdot c_1 = 6$$$ money for selling it.
- The fifth animal to be sold is animal $$$3$$$. Animal $$$a_3 = 4$$$ was sold before, so you receive $$$c_3 = 5$$$ money for selling it.

Your total profit, with this choice of permutation, is $$$12 + 4 + 14 + 6 + 5 = 41$$$. Note that $$$41$$$ is not the maximum possible profit in this example.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is present in the array).

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case description contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of animals.

The second line of the test case description contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq i$$$) — $$$a_i$$$ means the index of the animal that animal $$$i$$$ is afraid of.

The third line of the test case description contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — the costs of the animals.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
Output $$$t$$$ lines, each containing the answer to the corresponding test case. The answer should be $$$n$$$ integers — the permutation $$$p_1, p_2, \ldots, p_n$$$, indicating in which order to sell the animals in order to maximize the profit. If there are multiple possible answers, you can output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
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

Editorial:
Simple greedy observation: if at some point in time there exists an animal $$$i$$$ such that no one fears it (there is no index $$$a_j = i$$$), then it is optimal to sell that animal first.
Let's iteratively sell such animals as long as they exist. After selling animal $$$i$$$, we must additionally check if animal $$$a_i$$$ has become such that no one fears it, and if so, add it to the list for sale.
What will we get when we sell all such animals? Note that when there are no such animals left, $$$a_i$$$ will form a permutation, as each animal must be feared by at least one other animal.
As it is known, a permutation consists of cycles of the form $$$i \to a_i \to a_{a_i} \to \ldots \to i$$$.
Obviously, for each cycle we must solve the problem independently, and then combine the answers in any order. Note that if we sell animals in the order of the cycle, we will only receive a single payment for the last animal sold.
At the same time, it is not possible to obtain double payment for all animals in any case: the last animal sold from the cycle will always be sold for a single payment.
Therefore, it is optimal to sell all animals in the order of the cycle so that the animal with the minimum cost ends up being the last in this order.
You can see the implementation details in the code.