[Contest][1]
[Practice][2]
Author: [Shivam Garg][3]
Tester: [Shiv Dhingra][4]
DIFFICULTY
MEDIUM
PREREQUISITES
DP on Trees
PROBLEM
You are provided a tree, and each node has a value associated with it. For each query, start a path from the given node (considering it as root) till all the leaves. You need to pick two values Y and Z along the path such that Y comes before Z, and you purchase at price Y and sell at price Z. The node can be same as well where you purchase and sell. Find max profit for each query.
EXPLANATION
Go through this [tutorial][5] first to get a basic idea of DP on trees.
Consider 4 arrays - dp1 ( ), dp2( ), answ1( ), answ2( ).
arr ( ) will refer to value of the nodes.
We shall do this question by in-out DP i.e two DFS required- one for calculating answers from descendants, and the other one from ancestors/siblings.
For 1st DFS, we traverse from bottom (leaves) to top.
dp1(ind) stores the maximum value of any node in ind's subtree.
answ1(ind) stores the maximum value of profit that can be obtained from the subtree. In other words, answ1(ind) is max of answ1(all \hspace{1 mm}nodes\hspace{1 mm} in\hspace{1 mm} its\hspace{1 mm} subtree)
If ind is a parent node, and x is its child, then answ(ind)=max(answ(ind) , answ(x)) .
Also dp1[ind]=max(dp1[ind],dp1[x]) , dp1[ind]=max(dp1[ind],arr[ind]).
answ1(ind)=max(answ1(ind),max(0LL,dp1(ind)-arr(ind)))
With this, we can get the maximum profit if we travel from a given node towards its subtree.
Now, we need to compute the best possible answer from ancestors/siblings.
dp2(ind) stores max value of among all ancestors, and ancestors’ siblings.
answ2(ind) stores max profit that can be attained from ancestors/siblings.
answ2[x]=max(answ2[x],max(0LL,dp2[ind]-arr[x])) // from ancestor
answ2[x]=max(answ2[x],max(0LL,use-arr[x])) // use is equivalent to dp2[ ] but stores max profit from siblings.
For computing use, we need to store the maximum and second maximum dp1(children) values.
Whenever dp1(x)==maximum \hspace{1mm} of \hspace{1 mm} dp1(children) , we use second-maximum value to be stored in use variable.
Otherwise, the maximum value is used.
answ2(x)=max(answ2(x),use1) , answ2(x)=max(answ2(x),answ2(ind))
Here use1 has same purpose as use. The only difference is it stores either maximum or second maximum
answ1(children) values.
For updating dp2(x), dp2(x)=max(dp2(x),arr(x)) ,
dp2(x)=max(dp2(x),dp2(ind)),
dp2(x)=max(dp2(x),use)
All of this is done in top to bottom fashion in second DFS.
We keep updating answ2() and dp2().
The final answer will be max(answ1(ind),answ2(ind)).
Refer code for more details.
SOLUTION
Setter’s Solution -
[6]
[1]: https://www.codechef.com/CODR2018/problems/KRYP1/
[2]: https://www.codechef.com/problems/KRYP1/
[3]: http://codechef.com/users/shivamg_isc
[4]: http://codechef.com/users/lucifer2709
[5]: http://codeforces.com/blog/entry/20935
[6]: https://www.codechef.com/viewsolution/17468904