#2045. 蜘蛛爬树

    ID: 2045 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest764来源:qoj.ac数据:公开样例最短路径前缀和树上算法

蜘蛛爬树

蜘蛛爬树

题目描述

标题: 蜘蛛爬树 - Problem - QOJ.ac

#4924. 蜘蛛爬树

Statistics

问题描述

小 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。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 3 2
4 3 3 5
1 2 2
2 4 1
3 2 4
12 3
7 9
11
9