题解

思路

固定其他顶点后，一个顶点对目标函数的贡献是若干个绝对值函数之和，这是关于该顶点取值的凸函数。 凸函数在闭区间上的最大值一定可以在端点取得，因此每个顶点只需考虑选择 $l_v$ 或 $r_v$。

把树以顶点 $1$ 为根。令 $dp_{v,0}$ 与 $dp_{v,1}$ 分别表示顶点 $v$ 选择左端点或右端点时， 其子树内能够取得的最大贡献。每个孩子的选择相互独立，可分别取两种端点中贡献较大的一个。

做法

先用栈得到父子关系和遍历顺序，再按逆序处理顶点。对每条父子边，分别计算父亲取左、右端点时 孩子取两个端点的最佳贡献并累加。根节点两个状态的最大值就是答案。

正确性证明

由凸性结论，存在一个最优方案使所有顶点都选择区间端点，因此两状态不会遗漏最优解。

对任意顶点 $v$，在固定 $v$ 的端点后，不同孩子子树之间没有边相连，选择彼此独立。状态转移对每个 孩子同时比较孩子两种端点的子树最优值与当前边贡献，并选取较大者，所以恰好得到固定 $v$ 端点时 整个子树的最优值。按后序归纳到根节点，根的两个状态覆盖全部端点方案，取最大值即为全局最优解。

复杂度

每个顶点和每条边只处理常数次，单组时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。