[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
```