PROBLEM LINKS:
Setter : Vatsal Gupta##
Tester : Shubham Grover##
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Depth First Search,Segment Trees
EXPLANATION:
Firstly, here we use the thing that if we dfs a tree and we keep a stack such that
we push a element to the stack when we arrive at it and pop the element from the
stack when we depart from it, therefore when we depart from node x the
elements on the stack are the elements which lie on the path from root to x
(reader’s can easily prove this).
Here we use the same thing, we maintain an array (arr) of the maximum value in
the nodes and each index of this array works like the stack discussed above (i.e.
Suppose a node of value v is arrived we push the arrival time of this node to
arr[v] and next, suppose a node of value v is departed we pop the arrival time of
this node from arr[v]).
Now, all we need is the closest vertex with value greater than some value (x). For
that we have an array (arr2) of the maximum value in the nodes such that arr2[i]
stores the top of the stack at position i in “arr” array described above.
Now,we simply need the maximum value in the range (x,maximum
value in the nodes) which is actually the arrival time of the vertex closest to the
given vertex and has a value greater than the given value,
For this we apply segment tree to find the maximum value in a range and also we
apply point updates in the segment tree every time we arrive or depart a vertex
in the dfs run.
Since we can store the answer for each vertex beforehand in the dfs run we can
simply answer the queries in O(1) by maintaining an array such that the array[i]
stores the answer for the vertex i and update this array during the dfs run.
Total Complexity : O(Nlog(Max value)+Q)
SETTER’S SOLUTION:
Can be found here