[R50E]数据同步 - 代码源竞赛平台

时空限制

1S/512M

题目描述

某大型互联网公司拥有 $n$ 台核心服务器。由于业务存在依赖关系，第 $i$ 台服务器需要向第 $X_i$ 台服务器进行单向的高频数据同步。

为了防范地域性灾难，公司建立了两个地理位置独立的机房：数据中心 A 和 数据中心 B。必须为这 $n$ 台服务器分配数据中心（每台必须分配到 A 或 B 中的一个）。

为了提高数据安全性，分配必须满足下面的要求：

如果服务器 $i$ 及其同步目标服务器 $X_i$ 被分配到了同一个数据中心，一旦该数据中心宕机，这条同步链路将彻底瘫痪。为了防范这种风险，公司必须花费 $C_i$ 的预算，为服务器 $i$ 购买独立的云端异地备份。

反之，如果它们被分配在不同的数据中心，则天然满足跨机房容灾，无需额外花费。

求在最优的分配策略下，最小的总预算是多少？

格式

输入格式

第一行包含一个整数 $n$，表示核心服务器的数量。

接下来 $n$ 行，每行包含两个整数 $X_i$ 和 $C_i$，分别表示第 $i$ 台服务器的同步目标服务器编号，以及将它们分配在同一数据中心时所需的异地备份预算。

输出格式

输出一行一个整数，表示在最优的分配策略下，最小的总预算是多少。

样例

样例输入 #1

4
2 10
3 20
1 30
1 40

样例输出 #1

10

样例解释 #1

将 $1$ 号和 $2$ 号服务器分配在数据中心 A，将 $3$ 号和 $4$ 号服务器分配在数据中心 B。

• 对于 $1$ 号服务器，目标 $2$ 号也在 A，在同一个数据中心，需要花费 $10$ 的预算。
• 对于 $2$ 号服务器，目标 $3$ 号在 B，在不同数据中心，花费为 $0$。
• 对于 $3$ 号服务器，目标 $1$ 号在 A，在不同数据中心，花费为 $0$。
• 对于 $4$ 号服务器，目标 $1$ 号在 A，在不同数据中心，花费为 $0$。

总预算为 $10 + 0 + 0 + 0 = 10$，可以证明这是所有分配方案中的最小开销。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊限制	子任务依赖
$1$	$20$	$15$	无	无
$2$	$40$	$2 \times 10^5$	$X_i$ 互不相同
$3$	$40$		无	$1,2$

对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$1 \leq X_i \leq n$ 且 $X_i \not = i$，$1 \leq C_i \leq 10^9$。