Takahashi's Anguish

题目描述

有 $N$ 个人，编号为 $1$ 到 $N$。
Takahashi 决定选择一个序列 $P = (P_1, P_2, \dots, P_N)$，它是由 $1$ 到 $N$ 的整数组成的一个排列，并按顺序将糖果分别给 Person $P_1$、Person $P_2$、…、Person $P_N$。
由于第 $i$ 号人讨厌 Person $X_i$，如果 Takahashi 在给第 $i$ 号人之前先给了 Person $X_i$，那么第 $i$ 号人会获得 $C_i$ 的挫败值；否则，第 $i$ 号人的挫败值为 $0$.
Takahashi 可以任意选择 $P$. 问：他们的挫败值总和可能的最小值是多少？

输入格式

从标准输入给出如下格式的输入： $N$ $X_1$ $X_2$ $\dots$ $X_N$ $C_1$ $C_2$ $\dots$ $C_N$

输出格式

输出答案。

3
2 3 2
1 10 100

10

8
7 3 5 5 8 4 1 2
36 49 73 38 30 85 27 45

57

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq X_i \leq N$ $X_i \neq i$ $1 \leq C_i \leq 10^9$ 输入中的所有数值均为整数。如果他让 $P = (1, 3, 2)$，只有第 2 号人获得正的挫败值，此时挫败值总和为 $10$.
由于不可能使挫败值总和更小，答案为 $10$.

标签: AtCoder|abc256E

来源

AtCoder|abc256E