PROBLEM LINKS:Setter : Vatsal GuptaTester : Shubham GroverDIFFICULTY:MediumHard 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 asked 11 Oct '16, 12:52

My code is being showed as a wrong answer even though it is getting executed successfully with the sample input . Please tell me where am I making the mistake . Thank you . answered 11 Oct '16, 15:00
