3605: [CSP-S 2022] 数据传输transmit.cpp

小 C 正在设计计算机网络中的路由系统。
测试用的网络总共有 $n$ 台主机，依次编号为 $1\sim n$。这 $n$ 台主机之间由 $n-1$ 根网线连接，第 $i$ 条网线连接个主机 aia_iai 和 bib_ibi。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机 $a$ 能够直接将信息传输给主机 $b$ 当且仅当两个主机在可以通过不超过 $k$ 根网线直接或者间接的相连。
在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 $a$ 传输到主机 $b$（$a\ne b$），则其会选择出若干台用于传输的主机 c1=a,c2,…,cm−1,cm=bc_1 = a, c_2, \ldots, c_{m - 1}, c_m = bc1=a,c2,…,cm−1,cm=b，并按照如下规则转发：对于所有的 $1\le i<m$，主机 cic_ici 将信息直接发送给 ci+1c_{i + 1}ci+1。
每台主机处理信息都需要一定的时间，第 $i$ 台主机处理信息需要 viv_ivi 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为 ∑i=1mvci\sum_{i = 1}^{m} v_{c_i}∑i=1mvci。
现在总共有 $q$ 次数据发送请求，第 $i$ 次请求会从主机 sis_isi 发送数据到主机 tit_iti。小 C 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。

从文件 transmit.in 中读入数据。
输入的第一行包含三个正整数 $n,Q,k$，分别表示网络主机个数，请求个数，传输参数。数据保证 1≤n≤2×1051 \le n \le 2 \times {10}^51≤n≤2×105，1≤Q≤2×1051 \le Q \le 2 \times {10}^51≤Q≤2×105，$1\le k\le 3$。
输入的第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 viv_ivi，保证 1≤vi≤1091 \le v_i \le {10}^91≤vi≤109。
接下来 $n-1$ 行，第 $i$ 行包含两个正整数 ai,bia_i, b_iai,bi，表示一条连接主机 ai,bia_i, b_iai,bi 的网线。保证 1≤ai,bi≤n1 \le a_i, b_i \le n1≤ai,bi≤n。
接下来 $Q$ 行，第 $i$ 行包含两个正整数 si,tis_i, t_isi,ti，表示一次从主机 sis_isi 发送数据到主机 tit_iti 的请求。保证 1≤si,ti≤n1 \le s_i, t_i \le n1≤si,ti≤n，si≠tis_i \ne t_isi=ti。

输出到文件 transmit.out 中。
$Q$ 行，每行一个正整数，表示第 $i$ 次请求在传输的时候至少需要花费多少单位的时间。