# How to answer the following queries on a tree?

Given a tree of "N" nodes(each node has been assigned a value A[i],node-"1" is the root of the tree), and a constant "K" , 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 = 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 .

• Why not just precompute the answer for all nodes? Can you please also explain what you've tried and where the problem comes from? – Dmitry Jul 27 '20 at 4:41

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.