比赛场次 594
比赛名称 CSP2023-S模拟赛
比赛状态 已结束比赛成绩
开始时间 2023-10-18 12:30:00
结束时间 2023-10-18 14:30:00
开放分组 全部用户
注释介绍 16中场次
题目名称 坡伊踹
输入输出 poitry.in/out
时间限制 3000 ms (3 s)
内存限制 256 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分

坡伊踹

★★   输入文件:poitry.in   输出文件:poitry.out   简单对比
时间限制:3 s   内存限制:256 MiB

【题目背景】

Poitry 和 yrtiop 是一对好朋友。

【题目描述】

Poitry 有一棵树。树上每个点有点权 $a_i$,每条边有边权。 

定义 $dis(u, v)$ 表示 $u,v$ 两点在树上的最短距离。$Path(u,v)$ 表示 $u\to v$ 最短路径上出现的点的集合。 

yrtiop 有 $Q$ 个问题。每次它会给你一个点对 $\left \langle u,v \right\rangle$,它想知道 $\max\limits_{x\in Path(u,v)}\{a_x,dis(x,u) \}$ 的最小值。 

由于 Poitry 忙着薄纱 whk,所以这个简单的问题就交给你了。

【输入格式】

第一行两个整数 $n,q$,表示节点个数和询问次数。 

第二行 $n$ 个整数,表示 $a_1\sim a_n$。 

接下来 $n-1$ 行,每行三个整数 $u,v,w$,表示一条树边 $(u,v)$,边权为 $w$。

接下来 $q$ 行,每行两个整数 $u,v$,表示一次询问。

【输出格式】

共 $q$ 行,每行一个整数表示答案。

【样例输入】

7 4
9 5 7 1 3 8 7 
1 2 2
1 3 1
1 4 3
4 5 2
4 6 5
5 7 2
7 3
6 1
3 3
3 5

【样例输出】

3  
5
7
4

【样例下载】

样例下载

【数据规模与约定】

对于前 $30\%$ 的数据,保证 $1\le n, q \le 10^3$。 

另有 $15\%$ 的数据,保证所有树边满足 $u=1$。

另有 $15\%$ 的数据,保证所有树边满足 $v=u+1$。 

对于 $100\%$ 的数据,保证 $1\le n,q\le 2\times 10^5,1\le a_i\le 10^9,1\le w\le 10^6$。

【来源】

蒙德城算法竞赛 T1