Captain Flint and Treasure
Contest: Codeforces Round 660 (Div. 2)
Difficulty rating: 2000
Tags: data structures, dfs and similar, graphs, greedy, implementation, trees

Captain Fint is involved in another treasure hunt, but have found only one strange problem. The problem may be connected to the treasure's location or may not. That's why captain Flint decided to leave the solving the problem to his crew and offered an absurdly high reward: one day off. The problem itself sounds like this...

There are two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Initially, an $$$ans$$$ is equal to $$$0$$$ and the following operation is defined:

1. Choose position $$$i$$$ ($$$1 \le i \le n$$$);
2. Add $$$a_i$$$ to $$$ans$$$;
3. If $$$b_i \neq -1$$$ then add $$$a_i$$$ to $$$a_{b_i}$$$.

What is the maximum $$$ans$$$ you can get by performing the operation on each $$$i$$$ ($$$1 \le i \le n$$$) exactly once?

Uncle Bogdan is eager to get the reward, so he is asking your help to find the optimal order of positions to perform the operation on them.

Input format:
The first line contains the integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of arrays $$$a$$$ and $$$b$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$−10^6 \le a_i \le 10^6$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$ or $$$b_i = -1$$$).

Additional constraint: it's guaranteed that for any $$$i$$$ ($$$1 \le i \le n$$$) the sequence $$$b_i, b_{b_i}, b_{b_{b_i}}, \ldots$$$ is not cyclic, in other words it will always end with $$$-1$$$.

Output format:
In the first line, print the maximum $$$ans$$$ you can get.

In the second line, print the order of operations: $$$n$$$ different integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$). The $$$p_i$$$ is the position which should be chosen at the $$$i$$$-th step. If there are multiple orders, print any of them.

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

Example input:
3
1 2 3
2 3 -1

Example output:
10
1 2 3

Example input:
2
-1 100
2 -1

Example output:
99
2 1

Editorial:
Let's construct a graph $$$G$$$ with $$$n$$$ vertices and directed edges $$$(i; b_i)$$$.
Note that it is not profitable to process the vertex $$$i$$$ if the vertices $$$j$$$, for which $$$b_j=i$$$, have not yet been processed, since it is possible to process these vertices $$$j$$$ so that they will not decrease $$$a_i$$$.
We will do the following operation $$$n$$$ times:
Choose a vertex $$$V$$$ which does not contain any edge (there is always such a vertex due to an additional condition in the problem). Let's process it as follows:
• if $$$a_V> 0$$$, then apply the operation from the condition to this vertex. This is beneficial because if $$$b_v \neq -1 $$$ then we will improve the value of $$$a_{b_V}$$$.
• if $$$a_V \le 0$$$, then the value of $$$a_{b_V}$$$ will not improve, which means that it is profitable to apply the operation to the vertex $$$V$$$ after $$$b_V$$$ (if $$$b_V \neq -1$$$).
Let's store two containers $$$now$$$ and $$$after$$$. In $$$now$$$ we store the order of processing of vertices for which $$$a_V>0$$$. In $$$after$$$ - for which $$$a_V \le 0$$$. Then let's notice that the order $$$now + reverse (after)$$$ is appropriate to achieve the maximum answer.
Total $$$O(n)$$$ or $$$O(n \cdot log(n))$$$ depending on the implementation.