大佬们都在么，力助这道神秘题，拜托拜托

题目描述 小 C 正在设计计算机网络中的路由系统。 测试用的网络总共有 n 台主机，依次编号为1∼n。这 n台主机之间由 n−1 根网线连接，第 i 条网线连接个主机 ai 和 bi。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机 a 能够直接将信息传输给主机 b 当且仅当两个主机在可以通过不超过 k 根网线直接或者间接的相连。 在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 a 传输到主机 b（a != b），则其会选择出若干台用于传输的主机c1=a，c2,…,c(m−1)，c(m)=b，并按照如下规则转发：对于所有的 1≤i<m，主机 ci 将信息直接发送给 ci+1。 每台主机处理信息都需要一定的时间，第 i 台主机处理信息需要 vi 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为：

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

输入 输入的第一行包含三个正整数 n,Q,k，分别表示网络主机个数，请求个数，传输参数。数据保证 1≤n≤200000，1≤Q≤200000，1≤k≤3。 输入的第二行包含 n 个正整数，第 i 个正整数表示 vi，保证 1≤vi≤1000000000。 接下来 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 次请求在传输的时候至少需要花费多少单位的时间。

样例输入1
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

样例输出1
12

12
3