Last Updated: 22 Feb, 2021

Hide And Seek

Moderate

Asked in company

Solve now

Problem statement

Alice and Bob are best friends. They have spent their childhood in the beautiful city of Ninjaland.

The city has a total of N houses, including the King’s Castle. King’s Castle has address 1, and all other houses also have a unique address, say K(where 2<=K<=N).

There is always a unique path between any two houses, including the King’s Castle.

Alice and Bob love to play the Hide and Seek game. In the game, a person can hide in any house, including King’s Castle, and the second person has to find the first person. It’s Bob's turn to hide and Alice is supposed to find him.

Alice has a strategy, she will either go towards the King’s Castle and stop on reaching there or go away from King’s Castle, taking any possible path and stopping on reaching the last house. However, this strategy does not confirm that she will find Bob.

Alice is starting the game at some house say ‘X’ and Bob has hidden in some house say’ Y’.

You will be given queries of the following type and you have to determine whether Alice can find Bob or not.

0 X Y: Alice moves (0) towards the King’s Castle.

1 X Y: Alice movers (1) away from King’s Castle.

Return TRUE if Alice can find Bob else return FALSE.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of vertices. 

The next ‘N-1’ lines contain two single space-separated integers ‘U’ and ‘V’, denoting an edge from vertex ‘U’ to vertex ‘V’.

The next line will contain a single integer ‘Q’ representing the number of queries.

The next ‘Q’ lines will contain queries in the form as shown.

Output Format :

For each test case, print “YES” if Alice can find Bob, print “NO” if Alice can not find Bob.

The output of each test case will be printed in a new line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= X and Y <= N
1 <= Q <= 10^5
1 <= U,V <= N

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to check whether the first node falls in the subtree of the second node or not, here the first and second node will be determined based on the type of query.

If the query is of type ‘0’ then we will check whether ‘X’ is present in the subtree of ‘Y’ or not. If the query is of type ‘1’ then we will check whether ‘Y’ is present in the subtree of ‘X’ or not.

Now to find the subtrees of each node we will maintain two arrays which will store an in-time and an out-time during DFS calls. A node ‘A’ will be in the subtree of node ‘B’ if the in-time of ‘A’ is smaller than ‘B’ and the out-time of ‘A’ is greater than 'B’.

Algorithm :

Let’s say we have a graph ‘GRAPH’ in the form of an adjacency list.
Let’s initialize two global arrays of size ‘VERTICES+1’ say ‘ST_TIME’ and ‘EN_TIME’.
Initialize these arrays with 0 for each test case.
Fill the arrays using the DFS algorithm explained below.
DFS algorithm :
- Initialize an integer variable ‘TIME1’ = 0.
- Let’s say we have a recursive function DFS which takes 1 parameter that is current node say ‘U’.
- ‘ST_TIME[U]’ = ‘TIME1’.
- Increase ‘TIME1’ by 1.
- Iterate over ‘GRAPH[U]’ for 0 <= ‘i’ < ‘GRAPH[U]’.size() :
  - Initialize an integer variable ‘V’ = ‘GRAPH[U][i]’.
  - If ‘ST_TIME[V]’ is equal to 0 then do :
    - Make a recursive call with ‘V’.
    - Increase ‘TIME1’ by 1.
- ‘EN_TIME[U]’ = ‘TIME1’.
Iterate over the queries :
- If the query is of type '1' :
  - If ‘ST_TIME[X]’ > ‘ST_TIME[Y]’ and ‘EN_TIME[X]’ > ‘EN_TIME[Y]’ (checking if ‘Y’ falls in subtree of ‘X’ or not ) then do:
    - Return True.
  - Else
    - Return False.
If the query is of type '0' :
- If ST_TIME[Y] > ST_TIME[X] and EN_TIME[Y] > EN_TIME[X] ( checking if ‘X’ falls in subtree of ‘Y’ or not ) then do:
  - Return True.
- Else
  - Return False.

Solve now