# | User | Rating |
---|---|---|

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | wxhtxdy | 3329 |

4 | V--o_o--V | 3309 |

5 | Petr | 3297 |

6 | mnbvmar | 3255 |

7 | LHiC | 3250 |

8 | TLE | 3186 |

9 | Vn_nV | 3182 |

10 | dotorya | 3165 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 195 |

2 | Errichto | 179 |

3 | neal | 159 |

4 | Ashishgup | 157 |

5 | Petr | 155 |

5 | PikMike | 155 |

7 | majk | 154 |

8 | rng_58 | 153 |

8 | Um_nik | 153 |

10 | Vovuh | 150 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/17/2019 12:08:40 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

-Morass-

I think it could be solved by tree dp. dp(v) = answer for query(v).

We first root the tree at node 0. Assume u is child of v. We can see that if a[v] < a[u], we should always buy the product at v and sell it at u, you can always gain and even if you regret you can still buy it back without any loss a[u] = (a[u] — a[v]) + a[v]. If a[v] > a[u], obviously, there is no point buying at node v. So we could come up with dp(v) = max(dp[u] + max(0, a[u] — a[v])).

Then we run dfs again to to calculate dp(v) through its parent node. similar trick to the problem 4 in link.

It can be solved by

IN OUT dp. If you don't know about IN OUT dp please refer this video tutorial.Now coming to the solution of this problem: we will make two arrays here to solve the problem. 1. IN array — when we consider only the subtree of the node we are starting from. 2. OUT array — when we consider the rest of the tree

IN array:Here we can see that if at some node by going to any child of that node if we can gain maximum profit( val[child]-val[parent] > 0) we would go to that child, otherwise we will stop at that node and won't go further. we can use DFS for the calculation of the IN array. For a leaf node IN value would be zero and for internal nodes IN value would be for (all child of parent) IN[parent]=max( IN[parent] , IN[child]+max(0, val[child]-val[parent]) );OUT array:Here also dfs will be used. OUT[root of given tree]=0;To calculate OUT array we will first calculate the max(mx1) and second max(mx2) value of the IN values of all children of the current node we are visiting (Why? — please watch the video ). mx1 and mx2 are the max and second max value of IN[child]+max(0, val[child]-val[parent]);

Now for the current child of the node which is being visited the recurrence would be, OUT[child]=max( OUT[parent]+max(0,val[parent]-val[child]) , (mx1 or mx2) + max(0,val[parent]-val[child]) ).

at last for each node, if it is the root of the tree then the height will be max(IN[node], OUT[node]).

I know that it might be hard to understand the solution. I have followed the video and the way described in it. My Code: https://ideone.com/z6llzt