HELP Maximum Subtree

Правка en1, от ShashwatS1, 2019-05-11 10:37:12

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:-
print answers for each query.

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

Теги #segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ShashwatS1 2019-05-11 10:37:12 2694 Initial revision (published)