题目内容

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

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

现在，你可以交换任意节点的左右子树，使得树 $T$ 的先序遍历的平滑性最小。

输入描述

输入的第一行包含一个正整数 $n(n \leq 2000)$ 。

输入的第二行包含 $n$ 个正整数，第 $i$ 个正整数 $a_i$ 为节点 $i$ 的点权，保证 $1\le a_i \le 10^9$ 。

输入的第三行包含 $n-1$ 个正整数，第 $i$ 个正整数 $f_i$ 为节点 $i+1$ 的父节点，保证 $1 \le f_i\le i$ 且每个 $f_i$ 不会出现超过 $2$ 次。

我们约定 $f_i$ 第一次出现时，表示 $i+1$ 是 $f_i$ 的左儿子， $f_i$ 第二次出现时，表示 $i+1$ 是 $f_i$ 的右儿子。

输出描述

输出一个非负整数，即所求的最小平滑性。

样例

输入

5
1 2 3 4 5
1 1 2 2

输出

6

----------分割线------------

考场上的原数据$n \leq 4e5$ , 但是塔子哥还没有明确的解法。希望有大佬能提供标答

题解

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

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