4.数据传输（transmit）

题目描述

输入

输出

样例输入输出

输入#1 复制

7 3 3
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
1 2

输出#1 复制

12
12
3

提示

**【样例解释 \#1】**

对于第一组请求，由于主机 $4, 7$ 之间需要至少 $4$ 根网线才能连接，因此数据无法在两台主机之间直接传输，其至少需要一次转发；我们让其在主机 $1$ 进行一次转发，不难发现主机 $1$ 和主机 $4, 7$ 之间都只需要两根网线即可连接，且主机 $1$ 的数据处理时间仅为 $1$，为所有主机中最小，因此最少传输的时间为 $4 + 1 + 7 = 12$。

对于第三组请求，由于主机 $1, 2$ 之间只需要 $1$ 根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为 $1 + 2 = 3$。

**【数据范围】**

对于所有的测试数据，满足 $1 \le n \le 2 \times {10}^5$，$1 \le Q \le 2 \times {10}^5$，$1 \le k \le 3$，$1 \le a_i, b_i \le n$，$1 \le s_i, t_i \le n$，$s_i \ne t_i$。

| 测试点 | $n \le$ | $Q \le$ | $k =$ | 特殊性质 |
|:-:|:-:|:-:|:-:|:-:|
| $1$ | $10$ | $10$ | $2$ | 是 |
| $2$ | $10$ | $10$ | $3$ | 是 |
| $3$ | $200$ | $200$ | $2$ | 是 |
| $4 \sim 5$ | $200$ | $200$ | $3$ | 是 |
| $6 \sim 7$ | $2000$ | $2000$ | $1$ | 否 |
| $8 \sim 9$ | $2000$ | $2000$ | $2$ | 否 |
| $10 \sim 11$ | $2000$ | $2000$ | $3$ | 否 |
| $12 \sim 13$ | $2 \times {10}^5$ | $2 \times {10}^5$ | $1$ | 否 |
| $14$ | $5 \times {10}^4$ | $5 \times {10}^4$ | $2$ | 是 |
| $15 \sim 16$ | ${10}^5$ | ${10}^5$ | $2$ | 是 |
| $17 \sim 19$ | $2 \times {10}^5$ | $2 \times {10}^5$ | $2$ | 否 |
| $20$ | $5 \times {10}^4$ | $5 \times {10}^4$ | $3$ | 是 |
| $21 \sim 22$ | ${10}^5$ | ${10}^5$ | $3$ | 是 |
| $23 \sim 25$ | $2 \times {10}^5$ | $2 \times {10}^5$ | $3$ | 否 |

特殊性质：保证 $a_i = i + 1$，而 $b_i$ 则从 $1, 2, \ldots, i$ 中等概率选取。

5974: 4.数据传输（transmit）

题目描述

输入

输出

样例输入输出

提示

题目信息

模拟

数学与数论

动态规划

贪心

字符串

排序

枚举

数组与串

深搜

高精度

循环结构

递推

递归

二分三分

宽搜

背包

质数

线段树

分治

N进制

图论

队列

最短路

堆

树

并查集

栈

状态压缩

分支结构

几何

博弈论

生成树

顺序结构

离散化

hash表

位运算

单调队列

树状数组

KMP

字典树

二分图

数学期望

AC自动机

树链剖分

差分约束

数位动态规划

函数与过程

网络流

单调栈

前缀和