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

题解

首先第一个结论是：对于任意一个顶点，要么选择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

C++