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


POSTTREE - Editorial





Author: Ildar Gainullin
Tester: Oleksandr Kulkov
Editorialist: Prateek Gupta


Binary Lifting on a tree, lowest common ancestor, depth first search.




Given a tree with each node having some value. You need to find the cost of path from each node $v$ to the root of the tree. Cost of each node $u$ in path is the minimum of value of each node lying below u and is in path from $(u,\ v)$.


The problem involves using the concept of dynamic programming over a tree while moving from root to the bottom of the tree. Let $DP(x)$ denote the cost of path while moving from vertex $x$ to the root of the tree i.e $1$. While we arrive at node $x$, we have already calculated the DP values for all nodes in path from $1$ to $Parent[x]$. Now, for calculating the answer for node $x$, we need to find the greatest ancestor $y$ of $x$ in path from $1$ to $Parent[x]$, where all the nodes in path from $x$ to $y$ have their values greater than or equal to the given value of the node $x$.

If A[x] denotes the node value of x and cnt[x] denotes the number of nodes in path from $1$ to $x$, then the following equation holds true. $$DP(x) = DP(Parent[y]) + (cnt[x] - cnt[Parent[y])*A[x]$$

The only thing remaining is for each node x to calculate the greatest ancestor where all the nodes from node x to the ancestor have value greater than or equal to A[x]. One of the approaches is to pre-process this while calculating LCA and then apply binary lifting.

We define up[x][i] as the node that is ancestor of x at (2^i)-th distance from x. Then, $val[x][i]$ can be said as the minimum value of all the nodes from $x$ to up[x][i].

   set(up, -1)

   up[x][0] = Parent[x]
   for ( int i = 1 to 19 ) {
      if ( up[x][i - 1] != -1 ) {
          up[x][i] = up[up[x][i - 1]][i - 1]

   val[x][0] = min(A[x], A[Parent[x]]
   for ( i = 1 to 19 ) {
       if ( up[x][i] != -1 ) {
          val[x][i] = min(val[x][i - 1], val[up[x][i - 1]][i - 1])

Now, that we have preprocessed everything, how do we calculate the greatest ancestor of x such that minimum of values of nodes from x to this greatest ancestor in the path has value >= $A[x]$. This can be computed by binary lifting. For more details on binary lifting, check here. Anyways, let's proceed to look at the pseudo code.

    int vertex = x;
    for ( i = 19 to i = 0 ) {
        if ( up[vertex][i] != -1 ) {
            if ( val[vertex][i] >= A[x] ) {
              vertex = up[vertex][i];

Now, up[vertex][0] will be the node having value < A[x]. Hence, all nodes from vertex to x will be affected by A[x] and will use this value as their cost. You might want to look at the above DP equation written which might make a little more sense to you now.

For details on the implementation, have a look at the author or tester's solution.


Author solution can be found here.
Tester solution can be found here.

This question is marked "community wiki".

asked 28 May '17, 11:41

prateekg603's gravatar image

accept rate: 0%

edited 05 Jun '17, 16:22

Solution for this problem with binary lifting is great and the overall runtime is $O(nlogn)$ since you find the vertex $y$ of any vertex $x$ in $O(logn)$. I have a similar solution but I can reduce the runtime down to $O(n)$. You can see the implementation here: c++.

Here is a short explaination. This problem reminds me about the easier version of this problem that when the tree is a segment, the vertex $y$ of any vertex $x$ can be found using stack. My solution using a persistent-like stack. When you DFS to a child, you save the stack of the parent, and when you go back to the parent, just do rollback and continue DFS to another child. In my implementation, the operation push, pop, save and rollback run in $O(1)$. Each vertex you have to push it in the stack 1 time and the number of time you pop a vertex x equals to the direct child of the x. Since sum of direct child of all vertex equals to the number of the edges, that is, $n - 1$, hence overall complexity is $O(n + n - 1) = O(n)$.


answered 30 May '17, 15:39

darkkcyan's gravatar image

accept rate: 0%

edited 30 May '17, 20:35


Yes. Even I was thinking on the similar lines during contest, but wasn't able to design a proper solution. Nice Solution :)

(30 May '17, 16:05) lohit_974★

Please open the problems for practice section! Also please add the link to read about Binary Lifting.


answered 29 May '17, 18:22

lohit_97's gravatar image

accept rate: 4%

edited 29 May '17, 18:53


Hope this one helps

video link

(30 May '17, 16:53) swamicoder4★

In the above equation i think,

it should be DP(x)=DP(Parent[y])+(cnt[x]−cnt[Parent[y])∗A[x].


answered 30 May '17, 17:59

hacker_sk's gravatar image

accept rate: 14%

Thanks, corrected.

(05 Jun '17, 16:22) prateekg6035★

In the above code,

val[x][0] = min(A[x], A[Parent[x]])

for ( i = 1 to 19 ) {

if ( up[x][i] != -1 ) {

val[x][i] = min(val[x][i - 1], val[val[x][i - 1]][i - 1])



I think it should be,

val[x][0] = min(A[x], A[Parent[x]])

for ( i = 1 to 19 ) {

if ( up[x][i] != -1 ) {

val[x][i] = min(val[x][i - 1], val[up[x][i - 1]][i - 1])




answered 31 May '17, 03:33

rmm_0304's gravatar image

accept rate: 0%

Thanks, corrected.

(05 Jun '17, 16:22) prateekg6035★

implementation of editorial in C++ given below:


answered 31 May '17, 16:14

shloksingh10's gravatar image

accept rate: 0%

maybe the equation above need some fix.


answered 29 May '17, 19:24

microcosm2017's gravatar image

accept rate: 0%

For those who need a tutorial on binary lifting. I learnt it pretty much from here:

This answer is marked "community wiki".

answered 29 May '17, 19:53

ista2000's gravatar image

4★ista2000 ♦
accept rate: 20%

I too think the same hacker_sk


answered 31 May '17, 01:15

atuly's gravatar image

accept rate: 0%

Kindly someone please help me in finding the test case for which my code fails. All that i have tested passed but it is getting WA on submission. Link to my solution is


answered 31 May '17, 15:47

the_king_i_am's gravatar image

accept rate: 0%

Kindly someone please help.I am unable to find a bug in my approach.Link to my solution is already posted.If someone can find the test case for which my code fails it would be of great help for finding the failure point in the code.

(01 Jun '17, 22:26) the_king_i_am2★

@darkkcyan This is indeed a good approach. But the worst case time complexity of this solution is O(n^2). Look at this test case:
1 2 3 4 5 6 7 8 8 8 8 8 8 8
93 94 95 96 97 98 99 100 1 2 3 4 5 6 7.

The while loop inside the dfs function runs n/2 times for all n>=9 i.e for n/2 times.
Hence the time complexity is O(n+(n/2)*(n/2))=O(n^2). Correct me if I am wrong. Cheers ! :)


answered 01 Jun '17, 15:44

rahulladda's gravatar image

accept rate: 0%

as mentioned in the editorial:

Now, for calculating the answer for node x, we need to find the greatest ancestor y of x in path from 11 to Parent[x]Parent[x], where all the nodes in path from x to y have their values greater than or equal to the given value of the node x.

Is there a constraint that nodes in path from x to y NEED to have their values(which are given during input) greater than or equal to the given value of the node x?


answered 04 Jun '17, 21:46

codegod96's gravatar image

accept rate: 0%

why doesn't the setters code work??


answered 04 Jun '17, 23:09

drag's gravatar image

accept rate: 0%

weak test cases , even brute-force is passing the problem with a runtime of 0.06 which is having time limit of 2.0 sec ! my solution: posttree soln


answered 10 Jun '17, 17:44

docodon's gravatar image

accept rate: 0%

edited 10 Jun '17, 17:48

i tried this but getting WA in the last test case of second subtask.. if possible please help me with my code..


answered 26 Jul '17, 22:07

sidd845's gravatar image

accept rate: 0%

can anyone please explain a little bit how counts array is built?

i have implemented without this with the help of binary search ! but want to know this !


answered 20 Oct '17, 19:34

pk301's gravatar image

accept rate: 16% My solution using simple DP and dfs. I basically created two arrays, one storing all forward node information and the other one storing all backward node info.


answered 31 Jan '18, 02:18

shivan111'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: 28 May '17, 11:41

question was seen: 2,701 times

last updated: 31 Jan '18, 02:18