数据传输

题目描述:

小 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​ 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为 \(\sum_{i = 1}^{m} v_{c_i}\)。

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

输入格式:

输入的第一行包含三个正整数 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​。

输出格式:

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。

时间限制: 3000ms
空间限制: 1024MB

---

来源: CSP2022提高T4