题解
首先第一个结论是：对于任意一个顶点，要么选择l，要么选择r。因为选择某个l和r之间的值的情况只有一种：就是样例2中的那种。但是其实对于样例2，仍然可以选择l和r中的一个。
于是问题就是一个非常明确的dp问题。我们以0为树根。令dp[i][0]表示第i个节点选择l时的最大值；dp[i][1]表示第i个节点选择r时的最大值。于是有$$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|)$$
其中j是i的子节点。最终结果就是$\max(dp[0][0], dp[0][1])$。
代码
Java
Submission #117253790 - Codeforces
Codeforces. Programming competitions and contests, programming community
C++
Submission #117256624 - Codeforces
Codeforces. Programming competitions and contests, programming community