芬特队长参与了另一场寻宝活动,但只发现了一个奇怪的问题。问题可能与宝藏的位置有关,也可能无关。这就是为什么弗林特船长决定将解决问题的任务交给他的船员,并提供了一个高得离谱的奖励:一天休息。问题本身听起来是这样的......
有两个数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。最初,$$$ans$$$ 等于 $$$0$$$ 并且定义了以下操作:
1. 选择位置$$$i$$$ ($$$1 \le i \le n$$$);
2. 将 $$$a_i$$$ 添加到 $$$ans$$$;
3. 如果 $$$b_i \neq -1$$$ 则将 $$$a_i$$$ 添加到 $$$a_{b_i}$$$。
通过对每个 $$$i$$$ ($$$1 \le i \le n$$$) 执行一次操作,您可以获得的最大 $$$ans$$$ 是多少?
博格丹叔叔渴望得到奖励,所以他请求你帮助找到对它们执行操作的最佳位置顺序。
输入
第一行包含整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$−10^6 \le a_i \le 10^6$$$)。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$ 或 $$$b_i = -1$$$)。
附加约束:保证对于任何 $$$i$$$ ($$$1 \le i \le n$$$) 序列 $$$b_i, b_{b_i}, b_{b_{b_i}}, \ldots$$$ 不是循环的,换句话说,它总是以 $$$-1$$$ 结尾。
输出
在第一行中,打印您可以获得的最大$$$ans$$$。
在第二行中,打印操作顺序: $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。 $$$p_i$$$ 是第 $$$i$$$ 步骤应选择的位置。如果有多个订单,请打印其中任何一个。
示例
输入 #1
3 1 2 3 2 3 -1
输出 #1
10 1 2 3
输入 #2
2 -1 100 2 -1
输出 #2
99 2 1
输入 #3
10 -10 -1 2 2 5 -2 -3 -4 2 -6 -1 -1 2 2 -1 5 5 7 7 9
输出 #3
-9 3 5 6 1 9 4 10 7 8 2