English · Original
Chinese · Translation
Formal · Original
Medicine faculty of Berland State University has just finished their admission campaign. As usual, about $80\%$ of applicants are girls and majority of them are going to live in the university dormitory for the next $4$ (hopefully) years.
The dormitory consists of $n$ rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number $i$ costs $c_i$ burles. Rooms are numbered from $1$ to $n$.
Mouse doesn't sit in place all the time, it constantly runs. If it is in room $i$ in second $t$ then it will run to room $a_i$ in second $t + 1$ without visiting any other rooms inbetween ($i = a_i$ means that mouse won't leave room $i$). It's second $0$ in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.
That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that's not the case, mouse can be in any room from $1$ to $n$ at second $0$.
What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?
## Input
The first line contains as single integers $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of rooms in the dormitory.
The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^4$) — $c_i$ is the cost of setting the trap in room number $i$.
The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — $a_i$ is the room the mouse will run to the next second after being in room $i$.
## Output
Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.
[samples]
## Note
In the first example it is enough to set mouse trap in rooms $1$ and $4$. If mouse starts in room $1$ then it gets caught immideately. If mouse starts in any other room then it eventually comes to room $4$.
In the second example it is enough to set mouse trap in room $2$. If mouse starts in room $2$ then it gets caught immideately. If mouse starts in any other room then it runs to room $2$ in second $1$.
Here are the paths of the mouse from different starts from the third example:
* $1 \rightarrow 2 \rightarrow 2 \rightarrow \dots$;
* $2 \rightarrow 2 \rightarrow \dots$;
* $3 \rightarrow 2 \rightarrow 2 \rightarrow \dots$;
* $4 \rightarrow 3 \rightarrow 2 \rightarrow 2 \rightarrow \dots$;
* $5 \rightarrow 6 \rightarrow 7 \rightarrow 6 \rightarrow \dots$;
* $6 \rightarrow 7 \rightarrow 6 \rightarrow \dots$;
* $7 \rightarrow 6 \rightarrow 7 \rightarrow \dots$;
So it's enough to set traps in rooms $2$ and $6$.
Berland 国立大学的医学院刚刚结束了他们的招生工作。和往常一样，约 $80 %$ 的申请者是女生，她们中的大多数将在接下来的 $4$ 年（希望如此）里住在大学宿舍。
宿舍共有 $n$ 个房间和一只老鼠！女生们决定在某些房间设置捕鼠夹，以驱赶这个可怕的怪物。在第 $i$ 个房间设置一个捕鼠夹需要花费 $c_i$ 布尔。房间编号从 $1$ 到 $n$。
老鼠不会一直停留在原地，它会不停地移动。如果在第 $t$ 秒老鼠位于房间 $i$，那么在第 $t + 1$ 秒它会直接移动到房间 $a_i$，途中不经过任何其他房间（$i = a_i$ 表示老鼠不会离开房间 $i$）。初始时刻为第 $0$ 秒。如果老鼠进入了一个设置了捕鼠夹的房间，则会被捕获。
如果女生们知道老鼠的初始位置，这本可以很容易解决。但不幸的是，情况并非如此，老鼠在第 $0$ 秒时可能位于 $1$ 到 $n$ 中的任意一个房间。
女生们最少需要花费多少布尔，才能在某些房间设置捕鼠夹，从而保证无论老鼠从哪个房间开始，最终都会被抓住？
第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^5$）——宿舍的房间数量。
第二行包含 $n$ 个整数 $c_1, c_2, dots.h, c_n$（$1 lt.eq c_i lt.eq 10^4$）——$c_i$ 表示在第 $i$ 个房间设置捕鼠夹的花费。
第三行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq n$）——$a_i$ 表示老鼠在第 $i$ 个房间时，下一秒将移动到的房间编号。
请输出一个整数——女生们为保证无论老鼠从哪个房间开始，最终都会被抓住，所需设置捕鼠夹的最小总花费。
在第一个例子中，只需在房间 $1$ 和 $4$ 设置捕鼠夹即可。如果老鼠从房间 $1$ 开始，则立即被捕获；如果老鼠从其他任何房间开始，最终都会到达房间 $4$。
在第二个例子中，只需在房间 $2$ 设置捕鼠夹即可。如果老鼠从房间 $2$ 开始，则立即被捕获；如果老鼠从其他任何房间开始，则在第 $1$ 秒就会移动到房间 $2$。
以下是第三个例子中老鼠从不同起点出发的路径：
因此，只需在房间 $2$ 和 $6$ 设置捕鼠夹即可。
## Input
第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^5$）——宿舍的房间数量。第二行包含 $n$ 个整数 $c_1, c_2, dots.h, c_n$（$1 lt.eq c_i lt.eq 10^4$）——$c_i$ 表示在第 $i$ 个房间设置捕鼠夹的花费。第三行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq n$）——$a_i$ 表示老鼠在第 $i$ 个房间时，下一秒将移动到的房间编号。
## Output
请输出一个整数——女生们为保证无论老鼠从哪个房间开始，最终都会被抓住，所需设置捕鼠夹的最小总花费。
[samples]
## Note
在第一个例子中，只需在房间 $1$ 和 $4$ 设置捕鼠夹即可。如果老鼠从房间 $1$ 开始，则立即被捕获；如果老鼠从其他任何房间开始，最终都会到达房间 $4$。在第二个例子中，只需在房间 $2$ 设置捕鼠夹即可。如果老鼠从房间 $2$ 开始，则立即被捕获；如果老鼠从其他任何房间开始，则在第 $1$ 秒就会移动到房间 $2$。以下是第三个例子中老鼠从不同起点出发的路径： $1 arrow.r 2 arrow.r 2 arrow.r dots.h$； $2 arrow.r 2 arrow.r dots.h$； $3 arrow.r 2 arrow.r 2 arrow.r dots.h$； $4 arrow.r 3 arrow.r 2 arrow.r 2 arrow.r dots.h$； $5 arrow.r 6 arrow.r 7 arrow.r 6 arrow.r dots.h$； $6 arrow.r 7 arrow.r 6 arrow.r dots.h$； $7 arrow.r 6 arrow.r 7 arrow.r dots.h$； 因此，只需在房间 $2$ 和 $6$ 设置捕鼠夹即可。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of rooms.
Let $ c = (c_1, c_2, \dots, c_n) \in \mathbb{Z}^n $ be the cost vector, where $ c_i $ is the cost of placing a trap in room $ i $.
Let $ a = (a_1, a_2, \dots, a_n) \in \{1, 2, \dots, n\}^n $ be the transition function, where $ a_i $ denotes the room the mouse moves to from room $ i $ in one time step.
The transition defines a directed graph $ G = (V, E) $ with $ V = \{1, 2, \dots, n\} $ and $ E = \{(i, a_i) \mid i \in V\} $. Since each node has exactly one outgoing edge, $ G $ consists of disjoint cycles with trees directed toward them (functional graph).
**Constraints**
1. $ 1 \le n \le 2 \cdot 10^5 $
2. $ 1 \le c_i \le 10^4 $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \le a_i \le n $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the minimum total cost to select a subset $ T \subseteq V $ of rooms in which to place traps, such that for every starting room $ i \in V $, the mouse’s trajectory $ i \to a_i \to a_{a_i} \to \cdots $ eventually enters a room in $ T $.
Equivalently:
Select a minimum-cost set $ T \subseteq V $ such that every infinite path in $ G $ (which must eventually enter a cycle) intersects $ T $. This is equivalent to selecting at least one node from each cycle in $ G $, since trees feed into cycles and trapping any node in a cycle ensures all nodes leading to it are eventually caught.
Thus, for each cycle $ C $ in $ G $, choose the node $ v \in C $ with minimum cost $ c_v $, and sum these minima over all distinct cycles.
**Objective (Formal)**
Let $ \mathcal{C} $ be the set of all distinct cycles in $ G $.
For each cycle $ C \in \mathcal{C} $, define:
$$
\min_C = \min_{v \in C} c_v
$$
Then the minimal total cost is:
$$
\sum_{C \in \mathcal{C}} \min_C
$$
API Response (JSON)
{
"problem": {
"name": "D. Mouse Hunt",
"description": {
"content": "Medicine faculty of Berland State University has just finished their admission campaign. As usual, about $80\\%$ of applicants are girls and majority of them are going to live in the university dormito",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1027D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Medicine faculty of Berland State University has just finished their admission campaign. As usual, about $80\\%$ of applicants are girls and majority of them are going to live in the university dormito...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Berland 国立大学的医学院刚刚结束了他们的招生工作。和往常一样，约 $80 %$ 的申请者是女生，她们中的大多数将在接下来的 $4$ 年（希望如此）里住在大学宿舍。\n\n宿舍共有 $n$ 个房间和一只老鼠！女生们决定在某些房间设置捕鼠夹，以驱赶这个可怕的怪物。在第 $i$ 个房间设置一个捕鼠夹需要花费 $c_i$ 布尔。房间编号从 $1$ 到 $n$。\n\n老鼠不会一直停留在原地，它会不停地移动...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of rooms. \nLet $ c = (c_1, c_2, \\dots, c_n) \\in \\mathbb{Z}^n $ be the cost vector, where $ c_i $ is the cost of placing a trap in room $ i $...",
"is_translate": false,
"language": "Formal"
}
]
}