#P13278. [集训队互测 2022day12]蜘蛛爬树

    ID: 12461 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-点分治点分祖先维护距离LCA直线上包络单调栈二分查找向下取整与向上取整三角不等式

[集训队互测 2022day12]蜘蛛爬树

题目描述

给定一棵有 nn 个节点的带权树,将它复制为 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 的蛛丝。各棵树的树边相同,所有树边和蛛丝均可双向通过。

第 jj 只蜘蛛从全局编号为 sjs_j 的节点出发,爬到全局编号为 tjt_j 的节点。求每只蜘蛛的最短路长度。

输入格式

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

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 n−1n-1 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,表示原树的一条边连接 ui,viu_i,v_i,长度为 wiw_i。

接下来 qq 行,每行两个整数 sj,tjs_j,t_j,表示一次询问的起点和终点的全局编号。

输出格式

输出 qq 行,每行一个整数,表示对应的最短路长度。

样例

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

第一问可走 12→10→6→7→312\to10\to6\to7\to3,第二问可走 7→6→10→97\to6\to10\to9。图示见原 PDF。

数据范围

对于全部数据,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 n,m≤100n,m\le100,q≤1000q\le1000 3
2 n,q≤5000n,q\le5000 5
3 m≤20m\le20 11
4 原树为一条链 12
5 原树为菊花图 9
6 所有询问满足 sj=1s_j=1 22
7 n,q≤5×104n,q\le5\times10^4 18
8 无 20

原 PDF 题面