#89. 数据传输

数据传输

题目描述

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

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

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

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

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

输入格式

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

输入的第二行包含 nn 个正整数,第 ii 个正整数表示 viv_i,保证 1vi1091 \le v_i \le {10}^9

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

接下来 QQ 行,第 ii 行包含两个正整数 si,tis_i, t_i,表示一次从主机 sis_i 发送数据到主机 tit_i 的请求。保证 1si,tin1 \le s_i, t_i \le nsitis_i \ne t_i

输出格式

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

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
12
12
3

样例1解释

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

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

样例2

见选手目录下的 transmit2.intransmit2.ans

该样例满足测试点 22 的限制。

样例3

见选手目录下的 transmit3.intransmit3.ans

该样例满足测试点 33 的限制。

样例4

见选手目录下的 transmit4.intransmit4.ans

该样例满足测试点 2020 的限制。

数据范围

对于所有的测试数据,满足 1n2×1051 \le n \le 2 \times {10}^51Q2×1051 \le Q \le 2 \times {10}^51k31 \le k \le 31ai,bin1 \le a_i, b_i \le n1si,tin1 \le s_i, t_i \le nsitis_i \ne t_i

测试点 nn \le QQ \le k=k = 特殊性质
11 1010 22
22 33
33 200200 22
454 \sim 5 33
676 \sim 7 20002000 11
898 \sim 9 22
101110 \sim 11 33
121312 \sim 13 2×1052 \times {10}^5 11
1414 5×1045 \times {10}^4 22
151615 \sim 16 105{10}^5
171917 \sim 19 2×1052 \times {10}^5
2020 5×1045 \times {10}^4 33
212221 \sim 22 105{10}^5
232523 \sim 25 2×1052 \times {10}^5

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