codexr3455's blog

By codexr3455, history, 4 years ago, In English

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 .

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

it can be solved with segment tree on graph tree