时间限制： 2.0 秒

空间限制： 512 MB

题目描述

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

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

现在，你可以任意选择若干个节点并交换它们的左右儿子，使得树 $T$ 的先序遍历的平滑性最小。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$ 。

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

输入的第三行包含 $n-1$ 个正整数 $f_2,\cdots f_n$，其中 $f_{i}$ 为节点 $i$ 的父节点。

对于所有的 $2\le i\le n$，保证 $1\le f_i<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

样例 1 解释

在这组样例中，节点的编号即为点权，树的形态如图所示。

我们交换 $2$ 号节点和 $3$ 号节点，便可以得到一个平滑性最小的先序遍历序列 : $1~3~2~4~5$。

子任务

对于所有数据，保证 $1\le n\le 4\times 10^5,~1\le a_i\le 10^9$，输入的树一定为一棵二叉树。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。