QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100

# 4924. 蜘蛛爬树

统计

问题描述

小 F 在自家院子里种了一棵 $n$ 个节点的树。节点编号为 $1$ 到 $n$。有 $n-1$ 条边将这些节点连接起来,第 $i$ 条边连接节点 $u_i$ 与节点 $v_i$,长度为 $w_i$。

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

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

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

于是我们可以用一个序列 $a_1,a_2,\ldots,a_n$ 来描述这些蛛丝,其中 $a_x$ 表示对于任意 $1\le k < m$,连接 $(k,x)$ 与 $(k+1,x)$ 的蛛丝长度。

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

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

输入格式

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

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$,描述蛛丝长度。

接下来 $n-1$ 行,第 $i$ 行三个整数 $u_i,v_i,w_i$,描述第 $i$ 条边。

接下来 $q$ 行,第 $j$ 行两个整数 $s_j,t_j$,表示第 $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\text{ pt})$:$n\le 100,m\le 100,q\le 1000$
  • 子任务 $2\ (5\text{ pt})$:$n,q\le 5000$
  • 子任务 $3\ (11\text{ pt})$:$m\le 20$
  • 子任务 $4\ (12\text{ pt})$:树是一条链
  • 子任务 $5\ (9\text{ pt})$:树是一个菊花
  • 子任务 $6\ (22\text{ pt})$:$s_j=1$
  • 子任务 $7\ (18\text{ pt})$:$n,q\le 5\times 10^4$
  • 子任务 $8\ (20\text{ pt})$:无附加限制

对于 $100\%$ 的数据,$1\le n,q\le 2\times 10^5,1\le m\le 10^9,1\le a_x\le 10^9,1\le w_i\le 10^{12},1\le u_i,v_i\le n,1\le s_j,t_j\le n\times m$。