We have tree having node number from 1 to n (node 1 is root), each node have value(>0) and we have queries, in each query we have positive number x. For each query, find node number which value is strictly less than x ? (if there are multiple node print which is shortest from root of tree).
We can solve the problem by scan all queries then sort in reverse order and run a linear loop starting from root(1st index) to end of BF(breadth-first) sequence, simultaneously update query answer.
But what if there are updates involved of type (M G), replace value of node number M by G ?