Given a tree with \(N\) vertices and \(N - 1\) edges. \(i^{th}\) node has a value equal to \(A_i\) (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\)
6 3 1 5 7 8 6 10 1 2 1 3 2 4 2 5 3 6 1 6 2 7 6 2
7 8 -1
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor