eighty's blog

By eighty, history, 10 months ago, In English,

Hello Codeforces,

I am wondering how to solve this problem here.

Any idea? Thankyou.

  • Vote: I like it  
  • +2
  • Vote: I do not like it  

10 months ago, # |
  Vote: I like it +8 Vote: I do not like it
10 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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.

4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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