You are not logged in. Please login at to post your questions!


CLOVER - Editorial



Setter : Vatsal Gupta

Tester : Shubham Grover




Depth First Search,Segment Trees


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)


Can be found here

asked 11 Oct '16, 12:52

mightysg's gravatar image

accept rate: 0%

edited 02 Jan '17, 18:44

admin's gravatar image

0★admin ♦♦

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

vj2016's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 11 Oct '16, 12:52

question was seen: 940 times

last updated: 02 Jan '17, 18:44