Score : $500$ points

问题描述

设有 $N$ 名编号为 $1$ 到 $N$ 的人。
高桥决定选择一个整数序列 $P = (P_1, P_2, \dots, P_N)$，该序列是 $1$ 到 $N$ 的一个排列，并按照顺序将糖果送给第 $P_1$ 号、第 $P_2$ 号、$\dots$ 和第 $P_N$ 号的人。
由于第 $i$ 号人不喜欢第 $X_i$ 号人，如果高桥在送给第 $i$ 号人糖果之前先送给第 $X_i$ 号人，则第 $i$ 号人的沮丧值为 $C_i$；否则，第 $i$ 号人的沮丧值为 $0$。
高桥可以任意选择序列 $P$。请问他们的沮丧值之和的最小可能值是多少？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ people numbered $1$ through $N$.
Takahashi has decided to choose a sequence $P = (P_1, P_2, \dots, P_N)$ that is a permutation of integers from $1$ through $N$, and give a candy to Person $P_1$, Person $P_2$, $\dots$, and Person $P_N$, in this order.
Since Person $i$ dislikes Person $X_i$, if Takahashi gives a candy to Person $X_i$ prior to Person $i$, then Person $i$ gains frustration of $C_i$; otherwise, Person $i$'s frustration is $0$.
Takahashi may arbitrarily choose $P$. What is the minimum possible sum of their frustration?

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$X_1$ $X_2$ $\dots$ $X_N$

$C_1$ $C_2$ $\dots$ $C_N$

Output

Print the answer.

Sample Input 1

3
2 3 2
1 10 100

Sample Output 1

10

If he lets $P = (1, 3, 2)$, only Person $2$ gains a positive amount of frustration, in which case the sum of their frustration is $10$.
Since it is impossible to make the sum of frustration smaller, the answer is $10$.

Sample Input 2

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

Sample Output 2

57

update @ 2024/3/10 10:53:56