AtCoder——Subtree K-th Max

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500500 points

Problem Statement

We have a rooted tree with NN vertices. The vertices are numbered 11 through NN, and the root is Vertex 11.
The ii-th edge connects Vertices A_iAi​ and B_iBi​.
Vertex ii has an integer X_iXi​ written on it.

You are given QQ queries. For the ii-th query, given a pair of integers (V_i,K_i)(Vi​,Ki​), answer the following question.

• Question: among the integers written on the vertices in the subtree rooted at Vertex V_iVi​, find the K_iKi​-th largest value.

Constraints

• 2≤N≤105
• 0≤Xi​≤109
• 1≤Ai​,Bi​≤N
• 1≤Q≤105
• 1≤Vi​≤N
• 1≤Ki​≤20
• The given graph is a tree.
• The subtree rooted at Vertex V_iVi​ has K_iKi​ or more vertices.
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

NN QQ
X_1X1​ \ldots… X_NXN​
A_1A1​ B_1B1​
\vdots⋮
A_{N-1}AN−1​ B_{N-1}BN−1​
V_1V1​ K_1K1​
\vdots⋮
V_QVQ​ K_QKQ​

Output

Print QQ lines. The ii-th line should contain the response to the ii-th query.

---

Sample Input 1 Copy

Copy

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

Sample Output 1 Copy

Copy

4
5

The tree given in this input is shown below.

For the 11-st query, the vertices in the subtree rooted at Vertex 11 are Vertices 1, 2, 3, 41,2,3,4, and 55, so print the 22-nd largest value of the numbers written on these vertices, 44.
For the 22-nd query, the vertices in the subtree rooted at Vertex 22 are Vertices 2, 32,3, and 55, so print the 11-st largest value of the numbers written on these vertices, 55.

---

Sample Input 2 Copy

Copy

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 Copy

Copy

9
10

---

Sample Input 3 Copy

Copy

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

Sample Output 3 Copy

Copy

1
10
100
1000

---

 

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
inline int read()
{
	int x = 0, y = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-')  y = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		x = x * 10 + c - '0', c = getchar();
	return x * y;
}
 
typedef long long LL;

typedef pair<LL, LL> PII;
 
const int N = 200010;

int n, q;
int h[N], e[N], ne[N], a[N], mx[N][50], idx;
bool f[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int x)
{
	f[x] = true;
	mx[x][1] = -a[x];
	for(int i = h[x]; i != -1; i = ne[i])
	{
		if(!f[e[i]])
		{
			dfs(e[i]);
			for(int j = 1; j <= 20; j ++ )	mx[x][j + 20] = mx[e[i]][j];
			sort(mx[x] + 1, mx[x] + 40 + 1);
		}
	}
}

signed main()
{
	n = read(), q = read();
	memset(h, -1, sizeof h);
	for(int i = 1; i <= n; i ++ )  a[i] = read();
	for(int i = 1; i <= n - 1; i ++ )
	{
		int c, b;
		c = read(), b = read();
		add(c, b), add(b, c);
	}
	dfs(1);
	while(q -- )
	{
		int v, k;
		v = read(), k = read();
		printf("%d\n", -mx[v][k]);
	}
}