Hide And Seek

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
7 upvotes
Asked in company
Cerner Corporation

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

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

Sample Output 1 :

NO
YES
YES

Explanation For Sample Output 1 :

Example

For the first query :
Alice’s initial position: 7 and Bob’s initial position : 3 and '0' represent that Alice will go towards the Castle.
As we also know for any two given houses there is always a unique path so the path from 7 to 3 will be: 7 -> 4 -> 1 -> 3.
While following this path Alice will stop on reaching 1 (King’s Castle) and will not find Bob. So we will return FALSE.

For the second query :
Alice’s initial position: 4 and Bob’s initial position: 8 and '1' represent that Alice will go away from the Castle.
Now we can see there are three path which leads away from the Castle:
(i) 4 -> 6
(ii) 4 -> 5
(iii) 4 -> 7 -> 8
So Alice can find Bob if she follows the third path, we will return TRUE.

For the third query :
Alice’s initial position: 6 and Bob’s initial position: 1 and '0' represent that Alice will go towards the Castle.
As we also know for any two given houses there is always a unique path so the path from 6 to 1 will be: 6 -> 4 -> 1 and we can also see this from the graph.
While following this path Alice will stop on reaching 1 (King’s Castle) and will find Bob. So, we will return TRUE.

Sample Input 2 :

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

Sample Output 2 :

NO
YES
Hint

We just need to check subtrees and this further depends on the type of query.

Approaches (1)
Precomputation

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.
Time Complexity

O(N), where N is the number of vertices.

 

This is the time taken to precompute the in-time and out-time of DFS calls.

Space Complexity

O(N), where N is the number of vertices.

 

As we will use two arrays of the size of ‘N’ to store the in-time and out-time.

Code Solution
(100% EXP penalty)
Hide And Seek
Full screen
Console