Maximum depth | Practice Problems

Maximum depth

★★★★★

4.5

6 votes

Medium, Breadth First Search, BFS, Graphs, Algorithms, Binary Search

Details

Submissions

Discussion

Editorial

Problem

Given a tree with $N$ vertices and $N - 1$ edges. node has a value equal to (array indexing starts from 1). Given $Q$ queries of format, $L$ $X$ , find such node which lies at level $L\mod (Max Depth + 1)$ and has value which is just greater than or equal to $X$ . Answer to the query is the smallest value of such node and if no such node exists answer is -1.

Note: Root of the tree is 1 and its level is 0, MaxDepth is the maximum depth of the tree.

Input

First line: N, Q i.e no of vertices and no of queries respectively.

Second line: N space separated integers defining array $A$

Next N - 1 lines: u and v, meaning there is an edge between vertex u and v.

Next Q lines: Queries of type $L$ $X$ .

Output

For each query, print answer in a new line.

Constraints

$1 \leq N, Q \leq 2*10^{5}$

$1 \leq u,v \leq N$

$1 \leq A_i, X \leq 10^9$

$0 \leq L \leq N$

Sample Input

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

Sample Output

7
8
-1

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For query 1: nodes at level 1 are [2, 3] and node with a value just greater than or equal to 6 is 3, whose value is 7.

For query 2: nodes at level 2 are [4, 5, 6] and node with a value just greater than or equal to 7 is 4, whose value is 8.

For query 3: MaxDepth here is 2, so 6 % (2+1) = 0. And at level 0 there is only 1 node i.e 1 whose value is less than 2. So answer is -1.

Contributers:

Deepanshu Gandhi