小 C 正在设计计算机网络中的路由系统。
测试用的网络总共有 n 台主机,依次编号为 1 \sim n。这 n 台主机之间由 n - 1 根网线连接,第 i 条网线连接个主机 a_i 和 b_i。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率,主机 a 能够直接将信息传输给主机 b 当且仅当两个主机在可以通过不超过 k 根网线直接或者间接的相连。
在计算机网络中,数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 a 传输到主机 b(a \neq b),则其会选择出若干台用于传输的主机 c1 = a, c2, ..., cm-1, cm = b,并按照如下规则转发:对于所有的 1 ≤ i < m,主机 ci 将信息直接发送给 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 行,每行一个正整数,表示第 i 次请求在传输的时候至少需要花费多少单位的时间。
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, 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 中等概率选取。