dhruv_garg's blog

By dhruv_garg, history, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it