#5753. 「ROI 2026 Day1」分布式系统

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2026 Day1 T1. Распределенные системы

在一家公司里有 $n$ 台服务器，编号从 $1$ 到 $n$。第 $i$ 台服务器上运行着 $a_i$ 个服务。

由于服务器有时会发生宕机，因此为每台服务器都指定了备用服务器。对于编号为 $i$ 的服务器，其备用服务器的编号为 $p_i$。如果第 $i$ 台服务器满足 $p_i = i$，则它是一台高可靠性服务器，永远不会宕机。

对于任意两台不同的服务器 $i$ 和 $j$，它们的备用服务器编号 $p_i$ 和 $p_j$ 是不相同的。也就是说，$p$ 是一个长度为 $n$ 的排列，即 $1$ 到 $n$ 之间的每个数字在 $p_1, \dots, p_n$ 中恰好出现一次。

服务器宕机的处理过程如下：如果服务器 $i$ 宕机，原本在其上运行的所有服务都会迁移到编号为 $p_i$ 的服务器上，而服务器 $i$ 会被一台不运行任何服务的新服务器所替代。该服务器的编号及其备用服务器的编号保持不变。服务的迁移和服务器的更换过程非常迅速，在此期间不会发生新的宕机。

公司计划进行一次系统稳定性测试。为此，最多会让 $k$ 台服务器发生宕机。宕机是依次发生的，即不会有两台服务器同时宕机。请你确定，在不超过 $k$ 台服务器发生宕机后，单台服务器上可能存在的最大服务数量。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(1 \le k < n \le 10^5)$，分别表示服务器的总数和可能发生宕机的最大服务器数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \le a_i \le 10^9)$，表示每台服务器上运行的服务初始数量。

第三行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ $(1 \le p_i \le n)$，表示每台服务器对应的备用服务器编号。

输出格式

输出一个整数，表示问题的答案。

样例 1

输入

4 2
6 10 7 9
2 3 4 1

输出

26

让我们考虑在第一个样例中，能够达到最大答案的服务器宕机顺序。

首先，回顾一下当服务器发生宕机时，服务是如何迁移的：

第一步，第 $2$ 台服务器发生宕机，其服务迁移到第 $3$ 台服务器，此时第 $3$ 台服务器上共有 $10 + 7 = 17$ 个服务。

第二步，第 $3$ 台服务器发生宕机，其服务迁移到第 $4$ 台服务器，此时第 $4$ 台服务器上共有 $9 + 17 = 26$ 个服务。

为了更清晰地理解，请参考下表，表中记录了在上述过程中每台服务器上的服务数量变化：

如果先让第 $3$ 台服务器宕机，然后再让第 $2$ 台服务器宕机，过程如下：

此时单台服务器上的最大服务数量为 $16$，这并不是最优答案。

样例 2

输入

3 1
1000000000 993 2010
1 3 2

输出

1000000000

在第二个样例中，一种可能的方案是不让任何服务器宕机。此时第 $1$ 台服务器上有 $1000000000$ 个服务，这就是该样例的答案。由于所有的 $p_i = i$，这意味着所有服务器都是高可靠的，无法宕机。即使可以宕机，最大服务数量依然会在第 $1$ 台服务器上。

样例 3

输入

11 5
3 5 12 7 5 9 2 6 0 9 4
2 8 9 6 5 11 3 1 10 7 4

输出

23

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。