分数: 500 点
问题陈述
我们有一棵有根树 N 顶点。 顶点已编号 1 通过 N,根为 Vertex 1.
的 i第一条边连接顶点 A_i 和 B_i.
顶点 i 有一个整数
上面写着 X_i 。
你被给予 Q 查询。 对于 i-第一个查询,给定一对整数 (V_i,K_i),回答以下问题。
- 问题:以Vertex为根的子树中顶点上写入的整数之间 V_i,找到 K_i- 第一个最大值。
约束
- 2 \leq N \leq 10^5
- 0\leq X_i\leq 10^9
- 1\leq A_i,B_i\leq N
- 1\leq Q \leq 10^5
- 1\leq V_i\leq N
- 1\leq K_i\leq 20
- 给定的图是一棵树。
- 以顶点为根的子树 V_i 有 K_i 或更多顶点。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q
X_1 \ldots X_N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 K_1
\vdots
V_Q K_Q
输出
打印 Q 行。 的 i- 第行应包含对 i第一个查询。
示例输入 1
5 2 1 2 3 4 5 1 4 2 1 2 5 3 2 1 2 2 1
示例输出 1
4 5
此输入中给出的树如下所示。

对于 1-st 查询,以 Vertex 为根的子树中的顶点 1 是顶点 1, 2, 3, 4,和 5,所以打印 2-这些顶点上写入的数字的最大值, 4.
对于 2-nd查询,以Vertex为根的子树中的顶点 2 是顶点 2, 3,和 5,所以打印 1-这些顶点上写入的数字的最大值, 5.
示例输入 2
6 2 10 10 10 9 8 8 1 4 2 1 2 5 3 2 6 4 1 4 2 2
示例输出 2
9 10
示例输入 3
4 4 1 10 100 1000 1 2 2 3 3 4 1 4 2 3 3 2 4 1
示例输出 3
1 10 100 1000