← 返回题目列表

Codeforces · 1388/D

D. 弗林特船长和宝藏

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

芬特队长参与了另一场寻宝活动,但只发现了一个奇怪的问题。问题可能与宝藏的位置有关,也可能无关。这就是为什么弗林特船长决定将解决问题的任务交给他的船员,并提供了一个高得离谱的奖励:一天休息。问题本身听起来是这样的......

有两个数组 $$$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