maximum subtree

Правка en1, от dhruv_garg, 2019-05-10 09:54:06

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский dhruv_garg 2019-05-10 09:54:06 798 Initial revision (published)