### ShashwatS1's blog

By ShashwatS1, history, 5 months ago, ,

You are given a tree of A nodes having A-1 edges.Each node is numbered from 1 to A where 1 is root of tree. You are given Q queries. In each query, you will be given a unique integer j. You are required to remove the jth numbered edge from the tree. This operation will divide a tree into two different trees. For each query once you perform the remove operation you are asked to tell the maximum size among the sizes of the trees present till that query.

Note:-

1. once an edge is removed it will be considered removed for all the further queries.
2. it is guaranteed that each edge will be printing to exactly two different nodes of tree.
3. edges are numbered from 1 to A-1.

Input format:-

• first line input argument are an integer A denoting the number of nodes and an integer Q denoting number of queries.
• second & third argument are the integer arrays B & C where for each i (0 <= i <= A-1) , i denotes the (i+1)th edge and B[i] & C[i] are the nodes connected by it.
• fourth argument is an integer array D of distinct elements where D[i] denotes the number of edges to be removed for the ith query.

Output:-

Constraints:-

2<= A <= 10^5
1<= B[i] , C[i] <=A
1<= D[i] , Q <=A-1

Example:-

Input:
5 2
1 3 3 5
3 2 4 1
1 3

Output:-
3 2

• +5

 » 5 months ago, # |   0 How to solve this question?
 » 5 months ago, # | ← Rev. 2 →   +3 Try to remove all the edges that will be removed by the queries first. Then process the queries in reverse order. Now, instead of removing, you add the edge back into the tree and print the maximum tree size. You should be able to do this efficiently with the help of DSU data structure.
•  » » 5 months ago, # ^ |   0 that's sounds cool.....I solve it in a bit difficult way....
•  » » » 5 months ago, # ^ |   0 Care to share your solution?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   -18 ok ~~~~~
•  » » » » » 5 months ago, # ^ |   0 Can anybody explain me why my code gets down vote....??
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 1 . It's better to wrap large code snippets into spoilers. Like thisNow it doesn't take so much space on the page.2 . I suppose that saying "share your solution" LanceTheDragonTrainer wanted you to explain your idea like he did, instead of just posting large and unclear code here.
 » 2 months ago, # |   0 Can anyone share his/her code for the above problem because I'm stuck? Share your code.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Solution based on DSU approach suggested by "LanceTheDragonTrainer" (1st comment)-:https://ideone.com/lbqZyK
 » 2 months ago, # |   +1 Is there any online solution for this problem?
 » 2 months ago, # |   0 Alike problem: Ohani And The Link Cut Tree
 » 2 months ago, # |   0 http://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdfProblem "GALAKSIJA" has the same idea in it.