×

# CONTEST PANEL

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

# PREREQUISITES

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

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][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.

# SOLUTIONS

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

This question is marked "community wiki".

20421223
accept rate: 0%

 4 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 42●2 accept rate: 0% 1 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★

4★lohit_97
3428
accept rate: 4%

1

### Hope this one helps

(30 May '17, 16:53)

In the above equation i think,

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

1163
accept rate: 14%

Thanks, corrected.

(05 Jun '17, 16:22)
 1 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 4★rmm_0304 11●1 accept rate: 0% Thanks, corrected. (05 Jun '17, 16:22)
 1 implementation of editorial in C++ given below: https://www.codechef.com/viewsolution/13905914 answered 31 May '17, 16:14 31●1 accept rate: 0%
 0 maybe the equation above need some fix. answered 29 May '17, 19:24 1 accept rate: 0%
 0 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 link This answer is marked "community wiki". answered 29 May '17, 19:53 2.4k●7●22 accept rate: 20%
 0 I too think the same hacker_sk answered 31 May '17, 01:15 3★atuly 0 accept rate: 0%
 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 https://www.codechef.com/viewsolution/13905563 answered 31 May '17, 15:47 11●1 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)
 0 @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 ! :) answered 01 Jun '17, 15:44 21●2 accept rate: 0%
 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 1 accept rate: 0%
 0 why doesn't the setters code work?? answered 04 Jun '17, 23:09 3★drag 1●2 accept rate: 0%
 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 4★docodon 77●6 accept rate: 0%
 0 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 3★sidd845 25●4 accept rate: 0%
 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 2★pk301 627●10 accept rate: 16%
 0 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. answered 31 Jan '18, 02:18 10●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×1,672
×726
×253
×43
×5

question asked: 28 May '17, 11:41

question was seen: 2,701 times

last updated: 31 Jan '18, 02:18