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[1] = 10 A[2] = 20 A[3] = 30 A[4] = 40 A[5] = 50 A[6] = 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[1],A[2])=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[4],A[5],A[6]) = 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)