E - Subtree K-th Max Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

入力例 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

Score : 500 points

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.

figure

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