#P7237. [2023省队模拟]树

    ID: 7071 传统题 4000ms 888MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-树链剖分LCA普通线段树凸包单调栈查询排序合并有序结果

[2023省队模拟]树

题目描述

给定一棵 nn 个节点的树,节点编号为 11 到 nn。树上第 ii 条边连接节点 uiu_i 和 viv_i,长度为 wiw_i。

把这棵树复制 m−1m-1 次,得到 mm 棵相同的树并排成一行。第 kk 棵树上的第 xx 个节点记为 (k,x)(k,x),其全局编号是 (k−1)n+x(k-1)n+x。

对任意 1≤k<m1\le k<m、1≤x≤n1\le x\le n,节点 (k,x)(k,x) 和 (k+1,x)(k+1,x) 之间都有一条长度为 axa_x 的蛛丝。同一 xx 对应的蛛丝长度不随 kk 变化。

现在有 qq 只蜘蛛。第 jj 只蜘蛛要从全局编号为 sjs_j 的节点,沿树边和蛛丝爬到全局编号为 tjt_j 的节点。请分别计算它们的最短路径长度。

输入格式

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

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示蛛丝长度。

接下来 n−1n-1 行,第 ii 行三个整数 ui,vi,wiu_i,v_i,w_i,描述一条树边。

接下来 qq 行,第 jj 行两个整数 sj,tjs_j,t_j,表示起点和终点的全局编号。

输出格式

输出 qq 行,第 jj 行一个整数,表示第 jj 只蜘蛛的最短路径长度。

样例输入

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

样例输出

11
9

数据范围与约定

对于全部数据,1≤n,q≤2×1051\le n,q\le2\times10^5,1≤m≤1091\le m\le10^9,1≤ax≤1091\le a_x\le10^9,1≤wi≤10121\le w_i\le10^{12},1≤ui,vi≤n1\le u_i,v_i\le n,1≤sj,tj≤nm1\le s_j,t_j\le nm。

子任务 分值 特殊限制
1 3 n,m≤100n,m\le100,q≤1000q\le1000
2 5 n,q≤5000n,q\le5000
3 11 m≤20m\le20
4 12 树是一条链
5 9 树是一棵星形树
6 22 sj=1s_j=1
7 18 n,q≤5×104n,q\le5\times10^4
8 20 无特殊限制