Catch Pokemon

Ninja
0/200
Average time to solve is 60m
profile
Contributed by
2 upvotes
Asked in company
Ola

Problem statement

There are ‘N’ cities in Pokeland, and they are connected by ‘N-1’ roads. It is possible to reach from any city to any other city and there is a unique path between each pair of cities.

Each city has one Pokemon represented by an integer between 1 and 10^9. In each city. Given queries in the form of pairs of cities ‘U’ and ‘V’, find the number of Pokemon Ash catches while traveling from city ‘U’ to ‘V’. If he already has a Pokemon ‘X’ and he comes across it again, he does NOT catch it.

Note: Each query is independent, that is, he starts each query with zero Pokemon.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains 'T', denoting the number of test cases.
For each Test :
    The first line contains two space separated integers 'N' and ‘Q’, denoting the number of cities and the number of queries respectively.
The next N-1 lines contain a pair of cities ‘X’ and ‘Y’, indicating that there is a road between ‘X’ and ‘Y’.
The next line contains an array ‘P’ of ‘N’ integers, representing the type of Pokemon found in each city. 
The next ‘Q’ lines contain a pair of cities ‘U’ and ‘V’, indicating each query.
Output Format: 
Print Q lines, i.e, for each query print the number of Pokemon Ash catches in that travel.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints - 
1 <= 'T' <= 10
2 <= 'N' <= 10^4
1 <= ‘Q’ <= 10^5
1 <= X,Y,U,V <= N
1<= A[i] <= 10^9, i ∈ (1,N) 

Note - The sum of 'N' over all test cases does not exceed 10^4 and the sum of ‘Q’ does not exceed 10^5.

Time Limit: 1 sec
Sample Input 1:
1
5 2
1 2
1 3
2 4
2 5
1 2 3 3 4
4 3
1 5
Sample Output 1
3
3
Explanation for Sample Input 1:
For query 1:
The nodes on the path from 4 to 3 would be [4,2,1,3] and the Pokemon would be [3,2,1,3]. Since Ash already catches a Pokemon of type 3 in node 4, he does not catch the Pokemon at node 3. He ends his journey with 3 Pokemon.

For query 2:
The nodes on the path from 1 to 5 would be [1,2,5] and the Pokemon would be [1,2,4]. So, he ends his journey with 3 Pokemon.
Sample Input 2:
1
3 2
1 2
1 3
1 1 1
2 3
1 2
Sample Output 2:
1
1
Hint

For each pair of cities, what is the path between them?

Approaches (2)
Brute Force

Approach: For each query, we simulate the entire path between both the cities and count the number of unique Pokemon encountered on the path. This is our answer.

To efficiently be able to find the path between any two cities, say ‘A’ and ‘B’, we need to find their Lowest Common Ancestor (LCA). We can compute the LCA in multiple ways, including binary lifting and segment trees.

Once the LCA is computed, we can divide the journey into two paths, namely A to LCA and LCA to B (Corner case is when A or B itself is the LCA). We can traverse both these paths while using a set or a hashmap to keep track of the number of unique values.


 

Algorithm:

  • Apply a DFS on the tree and precompute the Binary lifting array as follows:
    • up[i][j] = up[up[i-1][j]][j-1]
  • Now, to find LCA for any pair of cities, we can use the Binary lifting table to find the Lowest node which is the ancestor of both the nodes.
  • For each pair of cities ‘A’, ‘B’, assign L = lca(A,B)
  • Assign Cur = A
  • While Cur is not equal to L
    • Insert Pokemon at Cur into a set
  • Assign Cur = B
  • While Cur is not equal to L
    • Insert Pokemon at Cur into a set
  • Assign Pokemon at L into the set
  • As a Set does not contain duplicate values, the size of the set is our answer.
Time Complexity

O(NlogN + Q*N), where ‘N’ is the number of cities and ‘Q’ is the number of queries.

It takes NlogN time for the binary lifting. For each query, we have to traverse the entire path between two cities, which can be N in the worst case.

Space Complexity

O(NlogN), where ‘N’ is the number of cities.

We need an array of size NlogN for the binary lifting.

Code Solution
(100% EXP penalty)
Catch Pokemon
Full screen
Console