题面
有编号从 $1$ 开始的 $n$ 个房间,有一只老鼠将会出现在某个房间中
当老鼠在某一时刻位于房间 $i$ $(1 \leq i \leq n)$ 时,它将在下一时刻抵达房间 $p_i$ (如果 $i = p_i$ 则代表老鼠不会离开 $i$ 房间)
已知在第 $i$ 个房间布置捕鼠夹的价格是 $w_i$,求最少需要花费多少能够使得无论老鼠从哪个房间出现,都会抵达有老鼠夹的房间。
输入格式
第一行输入一个整数 $n$ $(1 \leq n \leq 200000)$
第二行输入 $n$ 个整数 $w_i$ $(1 \leq w_i \leq 10000)$ 为在第 $i$ 个房间布置捕鼠夹的成本
第三行输入 $n$ 个整数 $p_i$ $(1 \leq p_i \leq n)$ 为在 $i$ 房间的老鼠即将抵达的房间编号
输出格式
输出一个整数,为满足条件的最小花费
输入样例1
5
1 2 3 2 10
1 3 4 3 3
输出样例1
3
输入样例2
4
1 10 2 10
2 4 2 2
输出样例2
10
输入样例3
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
输入样例3
2
样例解释
在第一组样例里可以选择房间1
和房间4
布置捕鼠夹。如果老鼠从房间1
出现,则会被房间1
的捕鼠夹捕获,否则会被房间4
的捕鼠夹捕获。
在第二组样例里可以在房间2
布置捕鼠夹,老鼠从任意房间出现,都会被房间2
的捕鼠夹捕获。
这是第三组样例中老鼠可能的行动轨迹:
1→2→2→…;
2→2→…;
3→2→2→…;
4→3→2→2→…;
5→6→7→6→…;
6→7→6→…;
7→6→7→…;
所以可以在房间2
和房间6
布置捕鼠夹