问题 D: 数据传输（transmit）

---

【题目描述】

【题目描述】
小 C 正在设计计算机网络中的路由系统。
测试用的网络总共有 n 台主机，依次编号为 1 ∼ n。这 n 台主机之间由 n − 1 根网线连接，第 i 条网线连接个主机 ai 和 bi。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机 a 能够直接将信息传输给主机 b 当且仅当两个主机在可以通过不超过 k 根网线直接或者间接的相连。
在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 a 传输到主机 b(a ≠ b)，则其会选择出若干台用于传输的主机 c1 = a, c2, · · · , cm−1, cm = b，并按照如下规则转发：对于所有的 1 ≤ i < m, 主机 ci 将信息直接发送给 ci+1。
每台主机处理信息都需要一定的时间，第 i 台主机处理信息需要 vi 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为  。
现在总共有 q 次数据发送请求，第 i 次请求会从主机 si 发送数据到主机 ti。小 C想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。
【输入格式】
从文件 transmit.in 中读入数据。
输入的第一行包含三个正整数 n, Q, k，分别表示网络主机个数，请求个数，传输参数。数据保证 1 ≤ n ≤ 2 × 10⁵ , 1 ≤ Q ≤ 2 × 10⁵ , 1 ≤ k ≤ 3。
输入的第二行包含 n 个正整数，第 i 个正整数表示 vi，保证 1 ≤ vi ≤ 10⁹。
接下来 n − 1 行，第 i 行包含两个正整数 ai , bi，表示一条连接主机 ai , bi 的网线。保证 1 ≤ ai , bi ≤ n。
接下来 Q 行，第 i 行包含两个正整数 si , ti，表示一次从主机 si 发送数据到主机 ti的请求。保证 1 ≤ si , ti ≤ n, si ≠ ti。
【输出格式】
输出到文件 transmit.out 中。
Q 行，每行一个正整数，表示第 i 次请求在传输的时候至少需要花费多少单位的时间。
【样例 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】
见选手目录下的 transmit/transmit2.in 与 transmit/transmit2.ans。
该样例满足测试点 2 的限制。
【样例 3】
见选手目录下的 transmit/transmit3.in 与 transmit/transmit3.ans。
该样例满足测试点 3 的限制。
【样例 4】
见选手目录下的 transmit/transmit4.in 与 transmit/transmit4.ans。
该样例满足测试点 20 的限制。
【数据范围】
对于所有的测试数据，满足 1 ≤ n ≤ 2×10⁵ , 1 ≤ Q ≤ 2×10⁵ , 1 ≤ k ≤ 3, 1 ≤ ai , bi ≤ n, 1 ≤ si , ti ≤ n, si ≠ ti。

测试点	n	Q	k	特殊性质
1	≤10	≤10	=2	是
2			=3
3	≤200	≤200	=2
4,5			=3
6,7	≤2000	≤2000	=1	否
8,9			=2
10,11			=3
12,13	≤2×105	≤2×105	=1
14	≤5×104	≤5×104	=2	是
15,16	≤105	≤105
17,18,19	≤2×105	≤2×105		否
20	≤5×104	≤5×104	=3	是
21,22	≤105	≤105
23,24,25	≤2×105	≤2×105		否

 
特殊性质：保证 ai = i + 1，而 bi 则从 1, 2, . . . , i 中等概率选取。
 

题目类型~

CSP2022-S 

咻咻~

提交答案 状态 返回作业