Denso Create Programming Contest 2022(AtCoder Beginner Contest 239)

E - Subtree K-th Max

Time Limit: 2 sec / Memory Limit: 1024 MB

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.

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

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

### 代码

#include <bits/stdc++.h>
#define SIZE 100010

using namespace std;

vector<int> max_20_value[SIZE];
int father[SIZE] = {0, 1};
vector<int> son[SIZE];

void creat_tree(int x)
{
{
if (father[i])
continue;
father[i] = x;
son[x].push_back(i);
creat_tree(i);
}
}

void calc_max_20_value(int x)
{
for (auto i : son[x])
{
calc_max_20_value(i);
for (auto j : max_20_value[i])
{
max_20_value[x].push_back(j);
}
}
sort(max_20_value[x].begin(), max_20_value[x].end());
while (max_20_value[x].size() > 20)
{
max_20_value[x].erase(max_20_value[x].begin());
}
}

int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, Q;
cin >> N >> Q;
for (int i = 1; i <= N; i++)
{
int X;
cin >> X;
max_20_value[i].push_back(X);
}
for (int i = 1; i < N; i++)
{
int A, B;
cin >> A >> B;
}
creat_tree(1);
calc_max_20_value(1);
for (int i = 1; i <= Q; i++)
{
int N, Q;
cin >> N >> Q;
cout << max_20_value[N][max_20_value[N].size() - Q] << endl;
}
return 0;
}