Subtree K-th Max

题目描述

我们有一棵有根树，包含 $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$ $\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

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$ 个顶点。 输入中的所有数值均为整数。该输入给出的树如下所示。 对于第 1 个询问，以顶点 $1$ 为根的子树中的顶点为顶点 $1, 2, 3, 4, 5$，所以输出这些顶点上数值的第 2 大，为 $4$。
对于第 2 个询问，以顶点 $2$ 为根的子树中的顶点为顶点 $2, 3, 5$，所以输出这些顶点上数值的第 1 大，为 $5$。

标签: AtCoder|abc239E

来源

AtCoder|abc239E