102394: [AtCoder]ABC239 E - Subtree K-th Max

Problem Statement

We have a rooted tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the root is Vertex $1$.
The $i$-th edge connects Vertices $A_i$ and $B_i$.
Vertex $i$ has an integer $X_i$ written on it.

You are given $Q$ queries. For the $i$-th query, given a pair of integers $(V_i,K_i)$, answer the following question.

• Question: among the integers written on the vertices in the subtree rooted at Vertex $V_i$, find the $K_i$-th largest value.

Constraints

• $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$
• The given graph is a tree.
• The subtree rooted at Vertex $V_i$ has $K_i$ or more vertices.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $i$-th line should contain the response to the $i$-th query.

Sample Input 1

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

Sample Output 1

4
5

The tree given in this input is shown below.

For the $1$-st query, the vertices in the subtree rooted at Vertex $1$ are Vertices $1, 2, 3, 4$, and $5$, so print the $2$-nd largest value of the numbers written on these vertices, $4$.
For the $2$-nd query, the vertices in the subtree rooted at Vertex $2$ are Vertices $2, 3$, and $5$, so print the $1$-st largest value of the numbers written on these vertices, $5$.

Sample Input 2

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

Sample Output 2

9
10

Sample Input 3

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

Sample Output 3

1
10
100
1000

问题描述

我们有一个有根树，有N个顶点。顶点编号为1到N，根顶点为1。

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

顶点i上写有一个整数X_i。

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

• 问题：在以顶点V_i为根的子树中，找出第K_i个最大的值。

限制条件

• 2 <= N <= 10^5
• 0<= X_i <= 10^9
• 1<= A_i, B_i <= N
• 1<= Q <= 10^5
• 1<= V_i <= N
• 1<= K_i <= 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个查询，以顶点1为根的子树中的顶点为顶点1、2、3、4和5，所以打印写在这些顶点上的数的第2个最大值，即4。

对于第2个查询，以顶点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