问题描述
小 F 在自家院子里种了一棵 n 个节点的树。节点编号为 1 到 n。有 n−1 条边将这些节点连接起来,第 i 条边连接节点 ui 与节点 vi,长度为 wi。
接下来的几天中,小 F 将这棵树复制了 m−1 份并排成一排,于是他拥有了 m 棵完全相同的树。第 k 棵树节点 x 的编号为 (k−1)×n+x。为方便叙述,下面用二元组 (k,x) 表示编号为 (k−1)×n+x 的节点。
小 F 的院子里有 q 只蜘蛛。这些蜘蛛会对于任意 1≤k<m,1≤x≤n,用一条蛛丝将 (k,x) 与 (k+1,x) 连接起来。
由于每个节点的高度和脆弱程度不同,这些蛛丝之间可能会有长短。但是由于这些树完全相同,且相邻树之间的距离相同,所以对于任意 1≤k1,k2<m,1≤x≤n,连接 (k1,x) 与 (k1+1,x) 的蛛丝长度等于连接 (k2,x) 与 (k2+1,x) 的蛛丝长度。
于是我们可以用一个序列 a1,a2,…,an 来描述这些蛛丝,其中 ax 表示对于任意 1≤k<m,连接 (k,x) 与 (k+1,x) 的蛛丝长度。
为了检验成果,蜘蛛们展开了一场爬树比赛。第 j 只蜘蛛要从节点 sj 沿树边和蛛丝爬到节点 tj。
你需要帮蜘蛛们算一算,每只蜘蛛的最短路径长度。
输入格式
第一行三个整数 n,m,q,分别表示每棵树的节点树、树的数量和蜘蛛数量。
第二行 n 个整数 a1,a2,…,an,描述蛛丝长度。
接下来 n−1 行,第 i 行三个整数 ui,vi,wi,描述第 i 条边。
接下来 q 行,第 j 行两个整数 sj,tj,表示第 j 只蜘蛛的起点和终点。
输出格式
输出 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
样例解释
3 棵树与蛛丝形成的结构如下(黑线表示树边,蓝线表示蛛丝):
第 1 只蜘蛛的一条最短路径如红色带箭头路径所示:
第 2 只蜘蛛的一条最短路径如红色带箭头路径所示:
数据规模与约定
- 子任务 1 (3 pt):n≤100,m≤100,q≤1000
- 子任务 2 (5 pt):n,q≤5000
- 子任务 3 (11 pt):m≤20
- 子任务 4 (12 pt):树是一条链
- 子任务 5 (9 pt):树是一个菊花
- 子任务 6 (22 pt):sj=1
- 子任务 7 (18 pt):n,q≤5×104
- 子任务 8 (20 pt):无附加限制
对于 100% 的数据,1≤n,q≤2×105,1≤m≤109,1≤ax≤109,1≤wi≤1012,1≤ui,vi≤n,1≤sj,tj≤n×m。