POSTTREE - Editorial

dfs
easy-medium
lca
ltime48
posttree

#1

PROBLEM LINK

Practice
Contest

CONTEST PANEL

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

PREREQUISITES

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

DIFFICULTY

EASY MEDIUM

PROBLEM

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).

EXPLANATION

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]* as the node that is ancestor of x at (2^i)-th distance from x.
Then, val[x]* can be said as the minimum value of all the nodes from x to up[x]*.

   set(up, -1)

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

 
   val[x][0] = min(A[x], A[Parent[x]]
   for ( i = 1 to 19 ) {
       if ( up[x]* != -1 ) {
          val[x]* = 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]* != -1 ) {
            if ( val[vertex]* >= A[x] ) {
              vertex = up[vertex]*;
            }
        }
    }

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.

SOLUTIONS

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


#2

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


#3

maybe the equation above need some fix.


#4

For those who need a tutorial on binary lifting. I learnt it pretty much from here: https://www.youtube.com/watch?v=kOfa6t8WnbI&t=971s


#5

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).


#6

In the above equation i think,

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


#7

I too think the same hacker_sk


#8

In the above code,

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

for ( i = 1 to 19 ) {

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

val[x] = 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]* != -1 ) {

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

}

}


#9

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 https://www.codechef.com/viewsolution/13905563


#10

implementation of editorial in C++ given below:
https://www.codechef.com/viewsolution/13905914


#11

@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:
15
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 ! :slight_smile:


#12

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?


#13

why doesn’t the setters code work??


#14

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


#15

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

https://www.codechef.com/viewsolution/14675743


#16

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 !


#17

https://www.codechef.com/viewsolution/17201285
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.


#18

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


#19

Hope this one helps

Link

video link


#20

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.