题目内容

给定一棵有 $n$ 个节点二叉树 $T$ ，树上的每个点 $i$ 有点权 $a_i$ 。

考虑二叉树下的先序遍历 $t = v_1,…,v_n$ ，我们定义其平滑性为

题解

假设我们在节点 $u$ , 左右节点分别为 $l,r$ . 如果先访问 $l$ 这一边，那么在 $l$ 中最后一个访问的节点，它需要和 $r$ 的值作绝对值差。之后访问 $r$ 时， $r$ 中最后一个访问的节点，它需要和之前的某个节点做差。

然后又观察到 $n$ 比较小。我们自然想到动态规划,一个维度存当前点，另一个维度存最后一个点要去和哪个点做差:

In following contests: