1000ms

Difficulty: 10

算法与标签>动态规划

会员专享

请先登录，开通会员或购买该题目所属题库（保研机考题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（保研机考题库），可解锁完整内容。

购买题库开通会员

题解

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

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

题目内容

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

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

In following contests:

保研/考研模拟赛第一场|清华大学(深圳)|2022年保研夏令营上机笔试