102564: [AtCoder]ABC256 E - Takahashi's Anguish
Description
Score : $500$ points
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
Input
题意翻译
存在 $ n $ 个人,你需要确定一个序列 $ P_n $ 表示这 $ n $ 个人的排列,对于每个人,第 $ i $ 个人有且仅有一个 $ x_i $,表示不喜欢 $ x_i $ 站在 $ i $ 的前面,若 $ x_i $ 站在 $ i $ 的前面则会产生 $ c_i $ 的不愉悦值,你需要确定排列以最小化不愉悦值之和,求最小值。Output
分数:500分
问题描述
有N个编号为1到N的人。
Takahashi决定选择一个序列$P = (P_1, P_2, \dots, P_N)$,该序列是1到N的整数的排列,并按照这个顺序将糖果分给Person $P_1$,Person $P_2$,$\dots$,和Person $P_N$。
由于Person $i$不喜欢Person $X_i$,如果Takahashi在分给Person $i$之前先分给Person $X_i$,那么Person $i$的挫败感会增加$C_i$;否则,Person $i$的挫败感为0。
Takahashi可以任意选择$P$。他们挫败感之和的最小可能值是多少?
约束
- $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$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $X_1$ $X_2$ $\dots$ $X_N$ $C_1$ $C_2$ $\dots$ $C_N$
输出
输出答案。
样例输入1
3 2 3 2 1 10 100
样例输出1
10
如果他让$P = (1, 3, 2)$,只有Person $2$获得正数挫败感,此时他们的挫败感之和为10。
由于无法使挫败感之和更小,答案为10。
样例输入2
8 7 3 5 5 8 4 1 2 36 49 73 38 30 85 27 45
样例输出2
57