Given a tree with n nodes and n - 1 edges initially and each edge is labelled. There are q queries for removing the edge i (i^{th} edge is guaranteed to be distinct and present currently in the tree). So removing the i edge will lead to split the tree into forest (disconnected trees). Now for each query I have to tell size of tree which has maximum number of nodes.
My approach : Brute force :
For each query, I will disconnect the i edge which is joining u_i and v_i. Then do dfs traversal on tree and count number of nodes each tree is having and take maximum of it.
Problem : Since the tree size can be large and query are also large then doing dfs every time is costly.
My Question : How to improve my approach to bring down time complexity? Kindly help.
Question Link : It was a private contest held yesterday and link is not available now.
Once you have the knowledge of disjoint set union, we can continue further.
Now think of the problem in reverse way, instead of breaking edges, first let us do union of the edges which are not the part of the query(edges which are never gonna break). Now process the queries in the reverse way (from the last).
For the ith query we have to merge that ith edge, but before merging we must have to find the answer (maximum of all subtrees), which we can find by using a multiset. Initially, the multiset contains ‘n’ number of ones(initially each of the node have size 1), later as we do merging, we will remove the individual sizes from the multiset and insert the combine size of their. Then easily we can print the last element from the multiset (the largest one).
I had taken the screenshot of my code from the yesterday’s contest, may be it will be helpful for you-
Thank you.