题目描述

$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$ 番目のクエリに対する答えを出力せよ。

题目大意

给定一棵 $n$ 个节点的树，每个节点的权值为 $x_i$。

现有 $Q$ 个询问，每个询问给定 $v,k$，求节点 $v$ 的子树第 $k$ 大的数。

$0\le x_i\le10^9,2\le n\le10^5,1\le Q\le10^5,1\le k\le20$。

翻译提供：xiaohaoaibiancheng66

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$ 個以上持つ
• 入力に含まれる値は全て整数である

Sample Explanation 1

この入力において与えられる木は下図のようなものです。  $1$ 番目のクエリでは、頂点 $1$ の部分木に含まれる頂点 $1,2,3,4,5$ に書かれた数のうち大きい方から $2$ 番目である $4$ を出力します。 $2$ 番目のクエリでは、頂点 $2$ の部分木に含まれる頂点 $2,3,5$ に書かれた数のうち大きい方から $1$ 番目である $5$ を出力します。