Can Someone help me here  asked 31 May '18, 04:39

The question has been closed for the following reason "The question is answered, right answer was accepted" by aryanc403 18 Oct '18, 03:45
You can refer this blog on dsu on trees. This problem is the one discussed in blog and provides you with various solutions. answered 31 May '18, 04:47
1
Thanks for blog and quick response.
(31 May '18, 04:53)
1
No problem. (Although don't mind my very late response).
(01 Jun '18, 14:48)

Here is the link to my code : https://repl.it/@NikhilAgrawal/lomsatgelral Basic logic is to compute the frequency of every color in the subtree of node and then find the color with maximum frequency and sum them. But the complexity will be greater than n^2 because for every node we have perform dfs(i.e. O(n) ). So, what can we do to reduce it's complexity? Every line of code seems to be normal and quite intuitive and naive at first sight. But what is special about this code??? To understand that you need to pay attention to line 20 and 21. Only these two lines contribute to reducing complexity from n^2 to n*log(n). But question is how? Notice that it's always the smaller map which gets added or merged with larger map. So, let's say there is a node A in map m. When smaller map is merged with larger map, minimum size of resulting map is 2*(size of smaller map). So, Every node at max gets added log(n) times. So the total complexity is nlog(n).* P.S : In my piece of code I have used INF and INF+1 to store the count of max color and it's sum respectively. answered 01 Jun '18, 17:42
