题目名称 3784. [CSP 2022S]数据传输
输入输出 csp2022_transmit.in/out
难度等级 ★★★★
时间限制 3000 ms (3 s)
内存限制 1024 MiB
测试数据 25
题目来源 Gravatarsyzhaoss 于2022-10-29加入
开放分组 全部用户
提交状态
分类标签
查看题解 分享题解
通过:1, 提交:8, 通过率:12.5%
Gravataryrtiop 100 16.425 s 0.00 MiB C++
Gravatar00000 68 27.479 s 0.00 MiB C++
Gravataryrtiop 56 4.550 s 0.00 MiB C++
Gravatarniko 0 0.026 s 0.00 MiB C++
Gravatarniko 0 3.623 s 0.00 MiB C++
Gravatarniko 0 3.755 s 0.00 MiB C++
Gravatarender 0 7.743 s 0.00 MiB C++
Gravatarender 0 42.631 s 0.00 MiB C++
本题关联比赛
CSP2022提高组
关于 数据传输 的近10条评论(全部评论)

3784. [CSP 2022S]数据传输

★★★★   输入文件:csp2022_transmit.in   输出文件:csp2022_transmit.out   简单对比
时间限制:3 s   内存限制:1024 MiB

【题目描述】

小 C 正在设计计算机网络中的路由系统。

测试用的网络总共有 $n$ 台主机,依次编号为 $1 \sim n$。这 $n$ 台主机之间由 $n - 1$ 根网线连接,第 $i$ 条网线连接个主机 $a_i$ 和 $b_i$。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率,主机 $a$ 能够直接将信息传输给主机 $b$ 当且仅当两个主机在可以通过不超过 $k$ 根网线直接或者间接的相连。

在计算机网络中,数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 $a$ 传输到主机 $b$($a \neq b$),则其会选择出若干台用于传输的主机 $c_1 = a, c_2, \ldots, c_{m - 1}, c_m = b$,并按照如下规则转发:对于所有的 $1 \le i < m$,主机 $c_i$ 将信息直接发送给 $c_{i + 1}$。

每台主机处理信息都需要一定的时间,第 $i$ 台主机处理信息需要 $v_i$ 单位的时间。数据在网络中的传输非常迅速,因此传输的时间可以忽略不计。据此,上述传输过程花费的时间为 $\sum_{i = 1}^{m} v_{c_i}$。

现在总共有 $q$ 次数据发送请求,第 $i$ 次请求会从主机 $s_i$ 发送数据到主机 $t_i$。小 C 想要知道,对于每一次请求至少需要花费多少单位时间才能完成传输。

【输入格式】

输入的第一行包含三个正整数 $n, Q, k$,分别表示网络主机个数,请求个数,传输参数。数据保证 $1 \le n \le 2 \times {10}^5$,$1 \le Q \le 2 \times {10}^5$,$1 \le k \le 3$。

输入的第二行包含 $n$ 个正整数,第 $i$ 个正整数表示 $v_i$,保证 $1 \le v_i \le {10}^9$。

接下来 $n - 1$ 行,第 $i$ 行包含两个正整数 $a_i, b_i$,表示一条连接主机 $a_i, b_i$ 的网线。保证 $1 \le a_i, b_i \le n$。

接下来 $Q$ 行,第 $i$ 行包含两个正整数 $s_i, t_i$,表示一次从主机 $s_i$ 发送数据到主机 $t_i$ 的请求。保证 $1 \le s_i, t_i \le n$,$s_i \ne t_i$。

【输出格式】

$Q$行,每行一个正整数,表示第 次请求在传输的时候至少需要花费多少单位的时间。

【样例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$。

【样例下载】

样例下载

样例2满足测试点 2 的限制。

样例3满足测试点 3 的限制。

样例4满足测试点 20 的限制。

【数据规模与约定】

对于所有的测试数据,满足 $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$。

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

【来源】

CSP 2022提高组 Task4