How to answer the following queries on a tree? Given a tree of &quot;N&quot; nodes(each node has been assigned a value A[i],node-&quot;1&quot; is the root of the tree), and a constant &quot;K&quot; , we have Q queries of the following type : [w]
(which means find the lowest valued node in the sub-tree of [w] , only considering those nodes in the sub-tree of [w] which have a depth less than equal to K) .
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 .
Without any precomputation, a depth-limited version of depth-first search would be a natural approach to this problem: then it's like finding the minimum of an array, you could find the minimum weight during the search. But a time-efficient way (if you have multiple queries for different nodes and $K$) is to indeed precompute the answer for all the nodes: a linear algorithm seems achievable, starting from the bottom level up to the root, level by level. You have to store for each node an array $a$ such as $a(K)$ gives the desired value. And if you modify the value of a node later, I think a backpropagation scheme could be also considered.