QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
[+6]

# 4924. 蜘蛛爬树

Statistics

问题描述

小 F 在自家院子里种了一棵 n 个节点的树。节点编号为 1n。有 n1 条边将这些节点连接起来,第 i 条边连接节点 ui 与节点 vi,长度为 wi

接下来的几天中,小 F 将这棵树复制了 m1 份并排成一排,于是他拥有了 m 棵完全相同的树。第 k 棵树节点 x 的编号为 (k1)×n+x。为方便叙述,下面用二元组 (k,x) 表示编号为 (k1)×n+x 的节点。

小 F 的院子里有 q 只蜘蛛。这些蜘蛛会对于任意 1k<m,1xn,用一条蛛丝将 (k,x)(k+1,x) 连接起来。

由于每个节点的高度和脆弱程度不同,这些蛛丝之间可能会有长短。但是由于这些树完全相同,且相邻树之间的距离相同,所以对于任意 1k1,k2<m,1xn,连接 (k1,x)(k1+1,x) 的蛛丝长度等于连接 (k2,x)(k2+1,x) 的蛛丝长度。

于是我们可以用一个序列 a1,a2,,an 来描述这些蛛丝,其中 ax 表示对于任意 1k<m,连接 (k,x)(k+1,x) 的蛛丝长度。

为了检验成果,蜘蛛们展开了一场爬树比赛。第 j 只蜘蛛要从节点 sj 沿树边和蛛丝爬到节点 tj

你需要帮蜘蛛们算一算,每只蜘蛛的最短路径长度。

输入格式

第一行三个整数 n,m,q,分别表示每棵树的节点树、树的数量和蜘蛛数量。

第二行 n 个整数 a1,a2,,an,描述蛛丝长度。

接下来 n1 行,第 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)n100,m100,q1000
  • 子任务 2 (5 pt)n,q5000
  • 子任务 3 (11 pt)m20
  • 子任务 4 (12 pt):树是一条链
  • 子任务 5 (9 pt):树是一个菊花
  • 子任务 6 (22 pt)sj=1
  • 子任务 7 (18 pt)n,q5×104
  • 子任务 8 (20 pt):无附加限制

对于 100% 的数据,1n,q2×105,1m109,1ax109,1wi1012,1ui,vin,1sj,tjn×m