8884: CSP-S2022 T4：数据传输（transmit）
[Creator : ]
Description
小 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$ 台主机，依次编号为 $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 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。
Input
输入的第一行包含三个正整数 $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$。
输入的第二行包含 $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$。
Output
$Q$ 行，每行一个正整数，表示第 $i$ 次请求在传输的时候至少需要花费多少单位的时间。
Constraints
对于所有的测试数据，满足 $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$ 中等概率选取。
|
测试点 |
$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$ |
否 |
Sample 1 Input
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
Sample 1 Output
12
12
3
对于第一组请求，由于主机 $4, 7$ 之间需要至少 $4$ 根网线才能连接，因此数据无法在两台主机之间直接传输，其至少需要一次转发；我们让其在主机 $1$ 进行一次转发，不难发现主机 $1$ 和主机 $4, 7$ 之间都只需要两根网线即可连接，且主机 $1$ 的数据处理时间仅为 $1$，为所有主机中最小，因此最少传输的时间为 $4 + 1 + 7 = 12$。
对于第三组请求，由于主机 $1, 2$ 之间只需要 $1$ 根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为 $1 + 2 = 3$。
对于第三组请求，由于主机 $1, 2$ 之间只需要 $1$ 根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为 $1 + 2 = 3$。
Sample 2 Input
10 10 3
835701672 912572995 368308854 156367225 251245604 788978650 385396264 960190423 51944511 479806606
2 1
3 2
4 2
5 3
6 3
7 2
8 7
9 1
10 9
1 7
1 5
2 1
1 9
10 5
3 10
2 9
10 2
1 4
4 7
Sample 2 Output
1221097936
1086947276
1748274667
887646183
939363946
900059971
964517506
1392379601
992068897
541763489