# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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
Milan = CF.pro;
it can be solved by using in-out dp on tree - in dp represents the max profit we can get considering only the sub-tree - while out dp represents max profit we can achieve by considering other siblings or the route through parent
You can see my code here https://ideone.com/vbejsW