#P18507. Top Cluster

Top Cluster

Top Cluster

Top Cluster 是一种在树上维护信息、支持高效范围查询的数据结构。Lovely EMmm 很喜欢数据结构技术,她正在学习 Top Cluster,并尝试解决下面的问题。请编写程序帮助她。

给定一棵有 nn 个顶点的树,顶点编号为 1,2,…,n1,2,\ldots,n。第 ii 个顶点的点权是非负整数 wiw_i,所有点权两两不同。

有 qq 次询问。第 ii 次给出顶点 xix_i 和非负整数 kik_i,请计算

$$\operatorname{mex}\{w_u\mid 1\le u\le n,\ \operatorname{dist}(u,x_i)\le k_i\}.$$

其中 dist⁡(u,v)\operatorname{dist}(u,v) 是树上从 uu 到 vv 的最短路径长度,即路径边权之和;集合的 mex(minimum excluded value,最小未出现值)是没有出现在集合中的最小非负整数。边界是 ≤ki\le k_i,包括恰好位于边界的顶点。

由于所有点权不同,一个非负整数没有出现在这个范围中,当且仅当它对应的唯一顶点位于范围外,或者它根本没有作为整棵树的点权出现。EMmm 已经发现了这一点,但还不知道如何继续,请帮助她完成查询。

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤5⋅1051\le n,q\le5\cdot10^5)。

第二行包含 nn 个整数 w1,…,wnw_1,\ldots,w_n(0≤wi≤1090\le w_i\le10^9),保证两两不同。

接下来 n−1n-1 行,每行三个整数 ui,vi,ℓiu_i,v_i,\ell_i(1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i,1≤ℓi≤1091\le\ell_i\le10^9),表示连接 ui,viu_i,v_i、长度为 ℓi\ell_i 的双向边。保证这些边构成一棵树。

接下来 qq 行,每行两个整数 xi,kix_i,k_i(1≤xi≤n1\le x_i\le n,0≤ki≤10150\le k_i\le10^{15}),表示一次询问。

输出格式

对每次询问输出一行,一个整数,表示相应集合的 mex。

完整原样例

5 4
3 9 0 1 2
1 2 10
3 1 4
3 4 3
3 5 2
3 0
1 0
4 6
4 7
1
0
3
4