Maximum Depth

Given a Tree of A nodes having A-1 edges.
Each node is numbered from 1 to A where 1 is the root of the tree.

You are given Q queries. In each query, you will be given two integers L and X. Find the value of such node which lies at level
L mod (MaxDepth + 1) and has value greater than or equal to X.

Answer to the query is the smallest possible value or -1, if all the values at the required level are smaller than X.

Note:

  1. It is guaranteed that each edge will be connecting exactly two different nodes of the tree.
  2. Edges are numbered from 1 to A-1. Please read the input format for more clarification.



Input Format

The first argument is an integer A denoting the number of nodes.

The second and third arguments are the integer arrays B and C where for each i (0 <= i < A-1), i denotes the (i+1)th edge and B[i] and C[i] are the nodes connected by it.

The fourth argument is an integer array D, where D[i] denotes the value of the (i+1)th node

The fifth and sixth arguments are the integer arrays E and F where for each i (0 <= i < Q), i denotes the (i+1)th query. E[i] denotes L and F[i] denotes X for (i+1)th query.

Output Format

Return an array of integers where the ith element denotes the answer to ith query.

Constraints

2 <= A, Q(size of array D and E) <= 10^5
1 <= B[i], C[i] <= A
1 <= D[i], E[i], F[i] <= 10^6 

Example

Input 1:
    A = 5
    B = 1 4 3 1
    C = 5 2 4 4
    D = 7 38 27 37 1
    E = 1 1 2
    F = 32 18 26

Output 1:
    [37 37 27]

Explanation:

      1[7]
     /    \
   5[1]  4[37]
        /    \
       2[38]  3[27]

    Query 1: 
    L = 1
    X = 32
    
    Nodes for level 1 are 5, 4
    Value of Node 5 = 1 < 32
    Value of Node 4 = 37 >= 32
    Ans = 37
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Maximum Depth on Interview Code Editor
Sign Up
to access hints and editorial solutions for Maximum Depth

Discussion


Loading...
Click here to start solving coding interview questions