| 比赛场次 | 593 |
|---|---|
| 比赛名称 | CSP2023-S模拟赛 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2023-10-17 17:00:00 |
| 结束时间 | 2023-10-17 22:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | rsr（op_组撒头屯） & lgc（yrtiop） 组题 |
| 题目名称 | 坡伊踹 |
|---|---|
| 输入输出 | poitry.in/out |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 256 MiB |
| 测试点数 | 20 简单对比 |
usr10086【题目背景】
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