2790. T4-[CSP-S 2022] 数据传输transfer
时间限制：3000 MS 内存限制：320 MB
题目描述
## 题目描述 小$ C$ 正在设计计算机网络中的路由系统。 测试用的网络总共有$ n$台主机，依次编号为$ 1∼n$。 这 $n$ 台主机之间由$ n-1$ 根网线连接，第$ i$条网线连接个主机$ ai$ 和$ bi$。 保证任意两台主机可以通过有限根网线直接或者间接地相连。 受制于信息发送的功率，主机 $a$能够直接将信息传输给主机 $b$ 当且仅当两个主机在可以通过不超过 $k$根网线直接或者间接的相连。 在计算机网络中，数据的传输往往需要通过若干次转发。 假定小 $C$需要将数据从主机 $a$传输到主机$ b（a\neb）$，则其会选择出若干台用于传输的主机$ c1=a,c2,\cdot\cdot\cdot,cm-1,cm=b$，并按照如下规则转发：对于所有的 $1\lei<m$，主机 $ci$ 将信息直接发送给 $ci+1$。 每台主机处理信息都需要一定的时间，第 $i$ 台主机处理信息需要 $vi$单位的时间。 数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。 据此，上述传输过程花费的时间为 $\sumi=1mvci$。 现在总共有 $q$ 次数据发送请求，第$ i$ 次请求会从主机 $si$发送数据到主机$ ti$。 小 $C$ 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。 ## 输入格式 输入的第一行包含三个正整数 $n,Q,k$，分别表示网络主机个数，请求个数，传输参数。数据保证 $1\len\le2\times105,1\leQ\le2\times105,1\lek\le3$。 输入的第二行包含 $n$个正整数，第$ i$ 个正整数表示$ vi$，保证$ 1\levi\le109$。 接下来$ n-1$ 行，第$ i$ 行包含两个正整数 $ai,bi$，表示一条连接主机 $ai,bi$ 的网线。保证 $1\leai,bi\len$。 接下来 $Q$行，第$ i$行包含两个正整数 $si,ti$，表示一次从主机 sisi 发送数据到主机$ ti$的请求。保证 $1\lesi,ti\len,si\neti$。 ## 输出格式 $Q$行，每行一个正整数，表示第$ i$ 次请求在传输的时候至少需要花费多少单位的时间。 ## 数据范围 对于所有的测试数据，满足$ 1\len\le2\times105,1\leQ\le2\times105,1\lek\le3,1\leai,bi\len,1\lesi,ti\len,si\neti$。  特殊性质：保证 $ai=i+1$，而 $bi$ 则从 $1,2,...,i$ 中等概率选取。 ```in4 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 ``` ```out4 12 3 ``` ## 说明 对于第一组请求，由于主机 $4,7$ 之间需要至少$ 4$根网线才能连接，因此数据无法在两台主机之间直接传输，其至少需要一次转发；我们让其在主机 11 进行一次转发，不难发现主机 $1$ 和主机$ 4,7$ 之间都只需要两根网线即可连接，且主机 $1$的数据处理时间仅为$ 1$，为所有主机中最小，因此最少传输的时间为$ 4+1+7=12$。 对于第三组请求，由于主机 $1,2$ 之间只需要 $1$根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为$ 1+2=3$