Ninja and Tree

Ninja
0/200
profile
Contributed by
1 upvote

Problem statement

You are given an undirected tree with ‘N’ vertices in the form of an array of ‘EDGES’ and ‘Q’ queries in ‘QUERIES’ array and root in the vertex ‘1’. You have also been given array ‘COLOR’ where ‘COLOR[i]’ represents the initial color of i-th vertex.

‘QUERIES’ is a 2D array where each row ‘QUERIES[i]’ represents a query of type ‘QUERIES[i][0]’.

You should process the queries of the two types:

1) Change the colours of all vertices in the subtree of the vertex ‘QUERIES[i][1]’ to the colour ‘QUERIES[i][2]’.

2) Find the number of different colours in the subtree of the vertex ‘QUERIES[i][1]’.

For Example: 
Let ‘N’ = 5, ‘EDGES’ = [[1, 2], [1, 3], [2, 4], [2, 5]], ‘QUERIES’ = [[1, 2, 3], [2, 1], [1, 3, 2], [2, 1]] and ‘COLOR’ = [1, 1, 1, 1, 1].
The initial tree will be:


After processing the query [1, 2, 3] i.e. colour all vertices in the subtree of 2 to 3.


Now the number of different colours in subtree of the vertex 1 is 2.
After processing the query [1, 3, 2] i.e. colour all vertices in the subtree of 3 to 2.


Now the number of different colours in subtree of the vertex 1 are 3.
Hence the answer to this test case is 2 and 3 (print on separate lines).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', which denotes the number of test cases.

The next line contains two integers ‘N’ and ‘Q’ denoting the number of vertices and the number of queries respectively.

The next line contains ‘N’ space-separated integers, ‘COLOR[i]’ denoting the initial colour of i-th vertex.

Each of the next N - 1 line contains two integers Uj, Vj (1 ≤ Uj, Vj  ≤ N) - the vertices of j-th edge.

The last ‘Q’ lines contain the description of the queries. Each description starts with the integer Tk (1 ≤ Tk ≤ 2) - the type of k-th query. 
For the queries of the first type then follows two integers Vk, Ck (1 ≤ Vk ≤ N, 1 ≤ Ck ≤ 60) - the number of the vertex whose subtree will be recoloured with the colour Ck.
For the queries of the second type then follows integer Vk(1 ≤ Vk ≤ N) - the number of the vertex for which subtree you should find the number of different colours.
Output Format : 
For each test case, return an array ‘ANS’, where ‘ANS[i]’ will denote the answer to i-th query of the second type.
Note : 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 ≤ T ≤ 10
1 ≤ N ≤ 1000
1 ≤ Q ≤ 1000
1 ≤ COLOR[i] ≤ 60

Time limit: 1 sec
Sample Input 1 :
2
5 4
1 1 1 1 1
1 2
1 3
2 4
2 5
1 2 3
2 1
1 3 2
2 1
3 2
1 1 1
1 2
1 3
1 2 2
2 1
Sample Output 1 :
2
3
2
Explanation of Sample Output 1 :
Test Case 1:
The initial tree will be:


After processing the query [1, 2, 3] i.e. color all vertices in subtree of 2 to 3.


Now the number of different colors in subtree of the vertex 1 are 2.
After processing the query [1, 3, 2] i.e. color all vertices in subtree of 3 to 2.


Now the number of different colors in subtree of the vertex 1 are 3.
Hence the answer to this test case is 2 and 3 (print on separate lines).

Test Case 2:
The initial tree will be:


After processing the query [1, 2, 2] i.e. color all vertices in subtree of 2 to 2.


Now the number of different colors in the subtree of the vertex 1 are 2.
Hence the answer to this test case is 2.
Sample Input 2 :
2
2 2
1 3
1 2
1 1 2
2 1
1 1
1
2 1
Sample Output 2 :
1
1
Explanation of Sample Output 2 :
Test Case 1:
The initial tree will be:


After processing the query [1, 1, 2] i.e. color all vertices in the subtree of 1 to 2.


Now the number of different colors in subtree of vertex 1 is 1. Hence answer to this testcase will be 1.

Test Case 2:
Initially, tree will be:


The number of different colors in the subtree of vertex 1 is only 1. Hence answer to this testcase will be 1.
Hint

Run DFS for each query.

Approaches (2)
Brute Force

The idea is simple, we process according to the problem statement. Initially we perform a DFS and find the parent of all vertices. This is required later while performing DFS we don’t end in an endless loop. 
 

While processing the first query we perform DFS from given vertex and update colors of all vertices in subtree.
 

While processing the second query we perform DFS from given vertex and insert colors of all vertices in subtree in set. And finally we will print size of this set.
 

The steps are as follows :

  1. Declare a 2D vector ‘adj’, which will store the adjacency list.
  2. for ‘i’ in [0, .. N - 2]:
    1. adj[EDGES[i][0]].push_back(EDGES[i][1])
    2. adj[EDGES[i][1]].push_back(EDGES[i][0])
  3. Declare an array ‘parent’ which will store parent of all vertices.
  4. Call dfsParent(1, 0, parent, adj).
  5. dfsParent(u, p, parent, adj):
    1. parent[u] = p
    2. for ‘v’ in adj[u]:
      1. if parent[v] is -1:
        1. dfsParent(v, u, parent, adj)
  6. for ‘i’ in [0, .. Q - 1]:
    1. if type is 1:
      1. Call dfsQuery1(QUERIES[i][1], parent[QUERIES[i][1]], QUERIES[i][2], COLOR, adj)
    2. if type is 2:
      1. Declare a set ‘s’.
      2. Call dfsQuery2(QUERIES[i][1], parent[QUERIES[i][1]], COLOR, adj, s)
      3. print size of set ‘s’.
  7. dfsQuery1(u, p, clr, COLOR, adj):
    1. COLOR[u] = clr
    2. for ‘v’ in adj[u]:
      1. if ‘v’ is not equal to ‘p’:
        1. dfsQuery1(v, u, clr, COLOR, adj)
  8. dfsQuery2(u, p, COLOR, adj, s):
    1. s.insert(COLOR[u])
    2. for ‘v’ in adj[u]:
      1. if ‘v’ is not equal to ‘p’:
        1. dfsQuery2(v, u, COLOR, adj, s)
Time Complexity

O( N * Q ), where ‘N’ and ‘Q’ are the number of vertices and the number of queries respectively.
 

We are doing DFS while processing every query and in worst-case DFS will have ~O( N ) time.

Hence the time complexity is O( N * Q ).

Space Complexity

O( N * Q ), where ‘N’ and ‘Q’ are the number of vertices and the number of queries respectively.
 

We are doing DFS while processing every query and in worst-case DFS will have ~O( N ) space for one query.

Hence the space complexity is O( N * Q ).

Code Solution
(100% EXP penalty)
Ninja and Tree
Full screen
Console