How to solve this tree query problem ? (related to Facebook Hackercup 2020,D2)

Revision en1, by codexr3455, 2020-07-28 17:05:36

Given a tree with "N" nodes(each node has been assigned value A[i]) , and a constant "K" ; we have Q queries of the following type : [w] , which means find the minimum valued node in the subtree of node [w], having depth less than "K".

The tree is rooted at node — "1" .

Example :

Value of nodes of tree : A = 10 A = 20 A = 30 A = 40 A = 50 A = 60

Edges of tree : [1-2], [2-3], [3-4], [4-5], [4-6]. K=2.

Query-1 : [w]=1 . All nodes in subtree of [w] : (1,2,3,4,5,6) , now, all nodes in sub-tree of [w] having depth less than equal to K : (1,2) . Hence , minimum(A,A)=min(10,20)=10 is the answer .

Query-2 : [w]=4 . All nodes in subtree of [w] : (4,5,6) , now, all nodes in sub-tree of [w] having depth less than equal to K : (4,5,6). Hence , minimum(A,A,A) = min(40,50,60)=40 is the answer . #### History

Revisions Rev. Lang. By When Δ Comment
en1 codexr3455 2020-07-28 17:05:36 931 Initial revision (published)