Editorial for Mock CCC '18 Contest 2 S5 - A Link/Cut Tree Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The key observation here is that the number of updates is small and the graph is relatively small.

After every update, we can recompute the maximum spanning tree of the graph. We can then do a DFS on the maximum spanning tree to answer queries in \mathcal O(N).


Comments

There are no comments at the moment.