-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

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