eighty's blog

By eighty, history, 18 months ago, , Hello Codeforces,

I am wondering how to solve this problem here.

Any idea? Thankyou. Comments (4)
 »
 » 18 months ago, # | ← Rev. 3 →   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.
 » 9 months ago, # | ← Rev. 2 →   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 treeIN 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;