Hello friends can someone tell me how to approach this problem ??
@vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299 @meooow @john_smith_3
Thanks in advance 
My approach was to find dfs order of tree and store it in array. While doing this dfs we can know the start and end of each vertex. When we write dfs order of a tree all nodes that are contained in subtree of a node lie within start_pos and end_pos of vertex in dfs order. After that I created queries of the form (l,r) where l=start_pos and r=end_pos of vertex in dfs order. After that I used square root decomposition and Mo’s algorithm to answer the queries.
1 Like
what are int co[200005],co1[200005]; in your solution? what exactly are they doing in the code can u please explain in detail the mo’s part?
co array is representing frequency of each colour and co1 array represents given the value, lets say=‘f’ how many colors are having frequency =“f”.
This was not the intended solution of the problem but it is quite good as it uses both dfs order property and Mo’s algo.
Hint 1:
Imagine we have a bag of colors. basically we need two maps. One to tell us frequency of a color x in sub-tree. Other one to tell us frequency of colors having frequency x.
Carefully observe what happens when a color is added. especially how the second map is affected by this insertion.
Hint 2:
You need to make this map using dfs of tree, merging smaller map to larger map to get O(N*log^2 N) complexity as map takes log factor and log for merging.
Similar problem http://codeforces.com/problemset/problem/940/F (Same concept, only difference, flat array instead of tree).
Click to view
Solution:
Nothing left, just elaborating map part.
Suppose we are going to add color c into map and frequency of color c in bag before insertion was f.
Now, after insertion, simply change frequency in first map. Let’s say frequency of color
In second map, frequency of f will decrease by 1, as there is one color less with frequency f. frequency of f2 will increase by 1, as there will be one more color with frequency f1.
Refer my solution here.
1 Like
@taran_1407 Thanks for the nice explanation. How did you added that hide/unhide textbox. Just curious 
Square root decomposition is quite useful. Thanks for your efforts.
Can u prove that the complexity will always be O(nlog^2n) plz?
Also in editorial,complexity mentioned is O(nlogn),so is ur merging somewhat different?
Complexity difference is because while writing hints, i thought about ordered maps, increasing complexity by log factor.
For NlogN, read about small to large trick. Merging into the largest child. That will make it clear why complexity is NlogN
There’s option called hide content @harrypotter0
1 Like