You are given a tree of A nodes having A-1 edges.Each node is numbered from 1 to A where 1 is the root of the tree. You are given Q queries . In each query you will be given a unique integer j. You are required to remove jth numbered edge from the tree . This operation divide the tree int two different trees .
for each query once you perfom the remove opeartion you are asked to tell the maximum size among all the sizes of the present till that query. Once an edge is removed it will be removed for further queries also.
example — A=5 edges — 1 — (1-2), 2-(1-3) , 3 (2-4) , 4 (3-5)
query — remove the 1st edge now tree will be divided into two subtree length 2 and 3 so answer would be 3.
A <=100000 q<=100000
Anyone.. thankyou.
A standard technique to use in situations requiring you to 'break a tree' is to think about the problem in the reverse direction.
That is, think that initially all the edges that you will eventually remove via the queries are already removed. Now process the queries in reverse order and this becomes classic DSU / Union-Find problem where you also have to maintain sizes of subtrees and a running maximum which keeps the answer after an edge has been added (merge operation).