Ninja and Tree

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)

In this approach, we first compute the startTime and endTime of each vertex and also we flatten the tree( convert it into an array ) using euler tour. 
 

Euler tour is basically a permutation of vertices on the basis of order of visiting by DFS starting from root. Easy to see that subtree of any vertex is a subsegment of that permutation.
 

After finding Euler tour we can query on this array for our query of type 2. We can get L and R value using startTime and endTime for each node. While generating Euler tour we also record the startTime and endTime for each node. So the L will be startTime and R will be endTime. startTime and endTime are just indices in Euler’s Tour. 
 

After this we update the Euler Tour to store the color of corresponding vertex. Hence we got a permutation of color, according to visiting by DFS.
 

Thus we just need to find the number of distinct values from L to R. Now this question is converted to a range - query and range - update form. We can think of Segment Tree with Lazy Propagation. 
 

Also note that the number of different colors is 60, so we can store the set of colours just as mask of binary bits in 64-bit type. So for a range we store if a color has appeared in that range or not. So for a particular bit, B_i that represents color, C_i - 0 represents C_i never appeared in the range, 1 represents that it appeared one or more times. 
 

While updating a node in Segment Tree the bit-mask of that node will be bitwise-OR of bit-mask of Right and Left child. So the anwer to our query will be just the number of 1s in binary representation of final mask.
 

Let us take an example of our Testcase 1 of Sample Input 1.

The Euler tour will be [1, 2, 4, 5, 3]. After we update it to store color it will be [1, 1, 1, 1, 1].
 

Now we will query on this array. We update color in subtree of 2 to 3. Hence the array will become [1, 3, 3, 3, 1].
 

Now we need to count the number of distinct values in subtree of 1. Now when we perform a query it will return 10. 10 is bitwise-OR of 2 and 8 (1 << 3). Remember while updating we will update it as (1 << C_i) because at i-th position there will be 1 denoting i-th color has appeared. So finally we will just count the number of 1s in the binary representation of 10. So the answer will be 2.
 

Now we perform another query and update color in subtree of 3 to 2. Hence the array will become [1, 3, 3, 3, 2].
 

Now when we perform query from [1, 5] it will return 14, which is bitwise-OR of 2, 8 and 4. So finally we will just count the number of 1s in binary representation of 14. So the answer will be 3.
 

The steps are as follows :

1. Declare a 2D vector ‘adj’, which will store the adjacency list.
2. for ‘i’ in [0, .. N - 2]:
   • adj[EDGES[i][0]].push_back(EDGES[i][1])
   • adj[EDGES[i][1]].push_back(EDGES[i][0])
3. Update the values of ‘COLOR’.
4. for ‘i’ in [0, .. N - 1]:
   • ‘COLOR[i]’ = 1 << COLOR[i]
5. Declare an array ‘startTime’ and ‘endTime’ of size ‘N’ + 1.
6. Declare an array ‘eulerTour’.
7. Call dfsEuler(1, 0 adj)
8. dfsEuler(u, p, adj):
   • ‘startTime[u]’ = eulerTour.size()
   • ‘eulerTour.push(u)’
   • for ‘v’ in adj[u]:
     • if ‘v’ is not ‘p’:
       • dfsEuler(v, u, adj)
   • ‘endTime’ = eulerTour.size() - 1
9. Update Euler Tour to store color of corresponding vertex.
10. for ‘i’ in [1, .. N]:
    • ‘eulerTour[i]’ = COLOR[eulerTour[i]]
11. Now build our segment tree on ‘eulerTour’ array.
12. Declare ‘answer’ array.
13. for ‘i’ in [0, .. Q - 1]:
    • Declare ‘type’ as ‘QUERIES[i][0]’
    • if ‘type’ is 1:
      • Perform range update in segment tree
      • Declare ‘vertex’ as ‘QUERIES[i][1]’ and ‘clr’ as ‘QUERIES[i][2]’
      • update(1, 1, n, startTime[vertex], endTime[vertex], 1 << clr)
      • The update function updates the value from the start time of ‘vertex’ to end time of vertex to 1 << clr.
    • if ‘type’ is 2:
      • Perform range query in segment tree.
      • Declare ‘vertex’ as ‘QUERIES[i][1]’ 
      • Declare ‘x’ to store value returned by this query.
      • ‘x’ = query(1, 1, n, startTime[vertex], endTime[vertex])
      • The query function returns the bitwise-OR of all values from start time of ‘vertex’ to end time.
      • Declare ‘ans’ to store count of 1s in binary representation of ‘x’.
      • while x > 0:
        • ‘ans’ += x % 2
        • x /= 2
      • answer.push(ans)