You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

给定一棵有 $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$ , 但是塔子哥还没有明确的解法。希望有大佬能提供标答