Any idea how to solve this question…

@vijju123,@anon55659401,@aryanc403,@ssjgz,@l_returns

Thanks in advance…

This can be solved using dsu on trees, wait for the editorial for more details.

Any good source to learn Dsu On Trees (Any video if you know)?

You can also solve it using Euler-Tour Traversal(or DFS) and using MO’s Algorithm. Refer to the **Problem 1** of this great tutorial. It is very much similar to this problem.

https://codeforces.com/blog/entry/44351

This was the best resource for dsu on trees that i could find.

It will seem a bit code heavy at first but its a nice blog.

Oh yes I didn’t noticed that It can be solved with MOs too thanks for sharing your approach

I used dsu on tree hld implementation by Arpa in codeforces blog. and used a struct given in geeksforgeeks for maintaining frequency , add/remove elements…

here is my submission :

https://www.codechef.com/viewsolution/27632848

Thanks, for providing the code also…

The simplest approach to code is using the Small to Large Technique as described in this problem: https://codeforces.com/contest/600/problem/E

Here’s my implementation: https://www.codechef.com/viewsolution/27630804