#P18507. Top Cluster
Top Cluster
Top Cluster
Top Cluster 是一种在树上维护信息、支持高效范围查询的数据结构。Lovely EMmm 很喜欢数据结构技术,她正在学习 Top Cluster,并尝试解决下面的问题。请编写程序帮助她。
给定一棵有 个顶点的树,顶点编号为 。第 个顶点的点权是非负整数 ,所有点权两两不同。
有 次询问。第 次给出顶点 和非负整数 ,请计算
$$\operatorname{mex}\{w_u\mid 1\le u\le n,\ \operatorname{dist}(u,x_i)\le k_i\}.$$其中 是树上从 到 的最短路径长度,即路径边权之和;集合的 mex(minimum excluded value,最小未出现值)是没有出现在集合中的最小非负整数。边界是 ,包括恰好位于边界的顶点。
由于所有点权不同,一个非负整数没有出现在这个范围中,当且仅当它对应的唯一顶点位于范围外,或者它根本没有作为整棵树的点权出现。EMmm 已经发现了这一点,但还不知道如何继续,请帮助她完成查询。
输入格式
第一行包含两个整数 ()。
第二行包含 个整数 (),保证两两不同。
接下来 行,每行三个整数 (,,),表示连接 、长度为 的双向边。保证这些边构成一棵树。
接下来 行,每行两个整数 (,),表示一次询问。
输出格式
对每次询问输出一行,一个整数,表示相应集合的 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