PROBLEM LINKCONTEST PANELAuthor: Ildar Gainullin PREREQUISITESBinary Lifting on a tree, lowest common ancestor, depth first search. DIFFICULTYEASY MEDIUM PROBLEMGiven 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)$. EXPLANATIONThe 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 preprocess 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].
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. SOLUTIONSAuthor solution can be found here.
This question is marked "community wiki".
asked 28 May '17, 11:41

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

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

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

implementation of editorial in C++ given below: https://www.codechef.com/viewsolution/13905914 answered 31 May '17, 16:14

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

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

@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: The while loop inside the dfs function runs n/2 times for all n>=9 i.e for n/2 times. answered 01 Jun '17, 15:44

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

weak test cases , even bruteforce 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

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

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

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
