P14401 [JOISC 2016] 电报 / Telegraph

JOI 诸岛是漂浮在太平洋上的一个小型群岛国家。JOI 诸岛共有 $N$ 个岛屿，编号从 1 到 $N$。 在 JOI 诸岛，岛屿之间的通信主要依靠无线电波进行。每个岛屿都配备了一台发射机和一台接收机。发射机可以向所有方向发送无线电波，但接收机只能接收来自特定方向的无线电波。因此，通过调整接收机的方向，可以改变它能接收来自哪个岛屿的无线电波。 目前，岛屿 $i$（$1 \le i \le N$）的接收机能够接收来自岛屿 $A_i$（$A_i \ne i$）的无线电波。此外，调整岛屿 $i$ 的接收机方向所需的成本为 $C_i$，与调整后的方向无关。 JOI 诸岛正在开展一项公共服务——电报服务。当岛屿 $i$（$1 \le i \le N$）的无线电波能够被岛屿 $j$（$1 \le j \le N, j \ne i$）的接收机接收时，岛屿 $i$ 可以通过无线电通信向岛屿 $j$ 发送电报。此外，电报可以通过若干岛屿中转发送。也就是说，当岛屿 $i$、岛屿 $j$、岛屿 $k$（$1 \le i, j, k \le N$，且 $i, j, k$ 互不相同）之间满足：岛屿 $i$ 可向岛屿 $j$ 发送电报，岛屿 $j$ 可向岛屿 $k$ 发送电报时，岛屿 $i$ 也可向岛屿 $k$ 发送电报。不允许使用无线电通信以外的方式发送电报。 作为 JOI 诸岛的通信大臣，你希望实现从任意岛屿向任意其他岛屿发送电报的目标。为此，可能需要调整若干岛屿接收机的方向。调整若干岛屿接收机方向所需的总成本，是各岛屿调整接收机方向所需成本的总和。 请计算为了实现从任意岛屿向任意其他岛屿发送电报的目标所需的最小成本。 **题目** 给定 JOI 诸岛的岛屿数量，以及每个岛屿接收机的相关信息，编写程序求出为了实现从任意岛屿向任意其他岛屿发送电报的目标所需的最小成本。

从标准输入读取以下数据： - 第 1 行包含一个整数 $N$。这表示 JOI 诸岛共有 $N$ 个岛屿。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含两个整数 $A_i$ 和 $C_i$，以空格分隔。这表示岛屿 $i$ 的接收机当前可以接收来自岛屿 $A_i$ 的无线电波，且调整其方向所需的成本为 $C_i$。

在标准输出中，输出一行，表示为了实现从任意岛屿向任意其他岛屿发送电报所需的最小成本。

### 样例解释 对于样例 1，将岛屿 2 的接收机方向调整为可接收来自岛屿 4 的无线电波。此时，即可实现从任意岛屿向任意其他岛屿发送电报，所需成本为 4。无论怎样调整接收机方向，成本都不可能低于 4，因此输出 4。 对于样例 2，首先，将岛屿 1 的接收机方向调整为可接收来自岛屿 4 的无线电波；接着，将岛屿 3 的接收机方向调整为可接收来自岛屿 2 的无线电波。此时，即可实现从任意岛屿向任意其他岛屿发送电报，所需成本为 $2 + 3 = 5$。无论怎样调整接收机方向，成本都不可能低于 5，因此输出 5。 对于样例 3，只需调整岛屿 1 和岛屿 3 的接收机方向即可。 对于样例 4，无需调整任何岛屿的接收机方向。 ### 限制 所有输入数据均满足以下条件： - $2 \le N \le 10^5$。 - $1 \le A_i \le N$（$1 \le i \le N$）。 - $A_i \ne i$（$1 \le i \le N$）。 - $1 \le C_i \le 10^9$（$1 \le i \le N$）。 ### 子任务 **子任务 1 [10 分]** - 满足 $N \le 10$。 **子任务 2 [30 分]** - 满足 $N \le 15$。 **子任务 3 [30 分]** - 满足 $N \le 3000$。 **子任务 4 [30 分]** 无额外限制。 翻译由 Qwen3-235B 完成