/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 から N の番号がついた N 人の人がいます。
高橋君は 1 から N までの整数を並び替えた列 P = (P_1, P_2, \dots, P_N) を 1 つ選んで、 人 P_1, 人 P_2, \dots, 人 P_N の順番に 1 人ずつキャンディを配ることにしました。
人 i は人 X_i のことが嫌いなので、高橋君が人 i より先に人 X_i にキャンディを配った場合、人 i に不満度 C_i がたまります。そうでない場合の人 i の不満度は 0 です。
高橋君が 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) とすれば不満度が正になるのは人 2 だけで、この時全員の不満度の和は 10 になります。
これより不満度の和を小さくすることはできないので、答えは 10 です。
入力例 2
8 7 3 5 5 8 4 1 2 36 49 73 38 30 85 27 45
出力例 2
57
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