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.
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 :
Thanks, for providing the code also…