3919. 坡伊踹

【题目背景】

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