当前没有测试数据。

E - 子树第K大

分数：$500$ 分

问题描述

给定一棵有 $N$ 个顶点的树。顶点编号从 $1$ 到 $N$，根为顶点 $1$。
第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。
顶点 $i$ 上有一个整数 $X_i$。

你将得到 $Q$ 个查询。对于第 $i$ 个查询，给出一对整数 $(V_i,K_i)$，回答以下问题。

• 问题：在以顶点 $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$ 个查询的回答。

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