题目描述

给定一棵 $n$ 个点的树，第 $i$ 个点处理信息的代价为 $v_i$。一次转发操作可以从当前点直接发送到树上距离不超过 $k$ 的点。对于每个请求 $(s,t)$，求从 $s$ 号点传到 $t$ 号点所需的最小总代价。

输入格式

本题原题采用文件读写，输入文件名为 transmit.in，输出文件名为 transmit.out。在 Hydro 上提交时，使用标准输入输出即可。

第一行包含三个整数 $n, Q, k$，分别表示树的节点数、请求数和最大转发距离。

第二行包含 $n$ 个正整数 $v_1, v_2, \dots, v_n$，表示每个点处理信息的代价。

接下来 $n-1$ 行，每行两个整数 $a_i, b_i$，表示树上的一条边。

接下来 $Q$ 行，每行两个整数 $s_i, t_i$，表示一个请求的起点和终点。

输出格式

输出 $Q$ 行，每行一个正整数，表示对应请求的最小总代价。

样例

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

来源

CSP-S 2022 第 4 题

数据范围与提示

• $1 \le n, Q \le 2 \times 10^5$
• $1 \le k \le 3$
• $1 \le v_i \le 10^9$