题目描述
给定一棵有 n 个节点的带权树,将它复制为 m 棵完全相同的树并排成一列。记第 k 棵树中的节点 x 为 (k,x),它的全局编号为 (k−1)n+x。
对于每个 1≤k<m 和 1≤x≤n,在 (k,x) 与 (k+1,x) 之间连一条长度为 ax 的蛛丝。各棵树的树边相同,所有树边和蛛丝均可双向通过。
第 j 只蜘蛛从全局编号为 sj 的节点出发,爬到全局编号为 tj 的节点。求每只蜘蛛的最短路长度。
输入格式
第一行三个整数 n,m,q,分别表示每棵树的节点数、树的棵数和询问次数。
第二行 n 个整数 a1,a2,…,an。
接下来 n−1 行,每行三个整数 ui,vi,wi,表示原树的一条边连接 ui,vi,长度为 wi。
接下来 q 行,每行两个整数 sj,tj,表示一次询问的起点和终点的全局编号。
输出格式
输出 q 行,每行一个整数,表示对应的最短路长度。
样例
4 3 2
4 3 3 5
1 2 2
2 4 1
3 2 4
12 3
7 9
11
9
第一问可走 12→10→6→7→3,第二问可走 7→6→10→9。图示见原 PDF。
数据范围
对于全部数据,1≤n,q≤2×105,1≤m≤109,1≤ax≤109,1≤wi≤1012,1≤ui,vi≤n,1≤sj,tj≤nm。
| 原题子任务 |
额外限制 |
分值 |
| 1 |
n,m≤100,q≤1000 |
3 |
| 2 |
n,q≤5000 |
5 |
| 3 |
m≤20 |
11 |
| 4 |
原树为一条链 |
12 |
| 5 |
原树为菊花图 |
9 |
| 6 |
所有询问满足 sj=1 |
22 |
| 7 |
n,q≤5×104 |
18 |
| 8 |
无 |
20 |
原 PDF 题面