题目内容

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

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

题解

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

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