How to solve this question? (SS5)


Any idea how to solve this question…
@vijju123,@anon55659401,@aryanc403,@ssjgz,@l_returns
Thanks in advance…

2 Likes

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

1 Like

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

1 Like

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.

2 Likes

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.

1 Like

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

1 Like

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

2 Likes

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