题目描述
给定一棵 n 个节点的树,节点编号为 1 到 n。树上第 i 条边连接节点 ui 和 vi,长度为 wi。
把这棵树复制 m−1 次,得到 m 棵相同的树并排成一行。第 k 棵树上的第 x 个节点记为 (k,x),其全局编号是 (k−1)n+x。
对任意 1≤k<m、1≤x≤n,节点 (k,x) 和 (k+1,x) 之间都有一条长度为 ax 的蛛丝。同一 x 对应的蛛丝长度不随 k 变化。
现在有 q 只蜘蛛。第 j 只蜘蛛要从全局编号为 sj 的节点,沿树边和蛛丝爬到全局编号为 tj 的节点。请分别计算它们的最短路径长度。
输入格式
第一行三个整数 n,m,q,分别表示每棵树的节点数、树的数量和询问数。
第二行 n 个整数 a1,a2,…,an,表示蛛丝长度。
接下来 n−1 行,第 i 行三个整数 ui,vi,wi,描述一条树边。
接下来 q 行,第 j 行两个整数 sj,tj,表示起点和终点的全局编号。
输出格式
输出 q 行,第 j 行一个整数,表示第 j 只蜘蛛的最短路径长度。
样例输入
4 3 2
4 3 3 5
1 2 2
2 4 1
3 2 4
12 3
7 9
样例输出
11
9
数据范围与约定
对于全部数据,1≤n,q≤2×105,1≤m≤109,1≤ax≤109,1≤wi≤1012,1≤ui,vi≤n,1≤sj,tj≤nm。
| 子任务 |
分值 |
特殊限制 |
| 1 |
3 |
n,m≤100,q≤1000 |
| 2 |
5 |
n,q≤5000 |
| 3 |
11 |
m≤20 |
| 4 |
12 |
树是一条链 |
| 5 |
9 |
树是一棵星形树 |
| 6 |
22 |
sj=1 |
| 7 |
18 |
n,q≤5×104 |
| 8 |
20 |
无特殊限制 |