Codeforces Round #722 Parsa's Humongous Tree Solution (Java/C++)

Solution:

The first conclusion is: for any vertex, it will choose l or r. Because if and only if the case like example 2 can choose value between l and r. But for the example 2, it still can choose l or choose r as solution.

Now the problem become an obviously clear DP problem. Let us set vertex 0 as the root of tree.
Let dp[i][0] to represent the maximum value when i-th vertex choose l; And let dp[i][1] to represent the maximum value when i-th vertex choose r. So, we have:$$dp[i][0]=\max(dp[j][0]+|l_j-l_i|, dp[j][1]+|r_j-l_i|)$$ $$dp[i][1]=\max(dp[j][0]+|l_j-r_i|, dp[j][1]+|r_j-r_i|)$$ Where j is a child node of i. And the answer is $\max(dp[0][0], dp[0][1])$.

Code:

Java

C++