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.

Thank you.