子树第 K 大

题目描述

我们有一棵包含 $N$ 个顶点的有根树。顶点编号为 $1$ 到 $N$,根是顶点 $1$。

第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

顶点 $i$ 上写着一个整数 $X_i$。

给定 $Q$ 个查询。对于第 $i$ 个查询,给定整数对 $(V_i,K_i)$,回答以下问题。

问题:在以顶点 $V_i$ 为根的子树中的顶点上写着的整数中,找出第 $K_i$ 大的值。

输入格式

输入按以下格式从标准输入给出:

N Q
X_1 … X_N
A_1 B_1
⋮
A_{N-1} B_{N-1}
V_1 K_1
⋮
V_Q K_Q

输出格式

输出 $Q$ 行。第 $i$ 行应包含对第 $i$ 个查询的回答。

样例

5 2
1 2 3 4 5
1 4
2 1
2 5
3 2
1 2
2 1

4
5

对于第 1 个查询,以顶点 $1$ 为根的子树中的顶点是顶点 $1, 2, 3, 4$ 和 $5$,所以输出这些顶点上写着的数中第 2 大的值,即 $4$。

对于第 2 个查询,以顶点 $2$ 为根的子树中的顶点是顶点 $2, 3$ 和 $5$,所以输出这些顶点上写着的数中第 1 大的值,即 $5$。

6 2
10 10 10 9 8 8
1 4
2 1
2 5
3 2
6 4
1 4
2 2

9
10

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

1
10
100
1000

数据范围

• $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$ 个或更多个顶点。
• 输入中的所有值均为整数。