题目内容

在一个树形的通信网络中，有 $n$ 个设备，编号为 $1$ 到 $n$。每个设备 $i$ 有一个优先级 $a_i$。网络中的设备通过 $n-1$ 条双向链路连接，且保证任意两个设备之间有唯一的一条简单路径相连。

现在需要从网络中选择一条简单路径（即路径上的设备不重复经过）。对于选定的路径，可以任选一端作为起点，按经过顺序记录沿途设备的优先级，得到一个数列。在该数列中，若存在两个位置 $i<j$ 且第 $i$ 个数字大于第 $j$ 个数字，则称它们构成一个“冲突对”。我们取一条路径所有可能数列中冲突对数量的最大值作为该路径的冲突对数量。求所有可能的简单路径中，冲突对数量的最大值。

数据范围：设备数量 $n$ 满足 $1 \le n \le 300$，优先级 $a_i$ 均为不超过 $10^5$ 的正整数。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 300$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)，依次表示设备 $1$ 至 $n$ 的优先级。 第三行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示设备 $i$ 与设备 $p_i$ 之间存在一条链路。保证 $1 \le p_i < i$。

输出描述

输出一个整数，表示所有简单路径中冲突对数量的最大值。

样例1

输入

1
42

输出

0

说明

设备数量 $n = 1$，网络中只有 1 个设备，不存在至少包含两个设备的简单路径，因此无法形成任何冲突对，最大冲突对数量为 0。

样例2

输入

3
3 1 2
1 2

输出

2

说明

设备优先级分别为 $a_1 = 3$、$a_2 = 1$、$a_3 = 2$，树形结构为一条链 $1 - 2 - 3$。

所有简单路径及其冲突对情况：

• 路径 $1 \to 2$：数列 $[3, 1]$，冲突对为 $(3,1)$，数量 1。
• 路径 $2 \to 3$：数列 $[1, 2]$，无冲突对，数量 0。
• 路径 $1 \to 2 \to 3$：数列 $[3, 1, 2]$，冲突对有 $(3,1)$ 和 $(3,2)$，数量 2。
• 其他路径的冲突对数量均不超过 2。

因此所有简单路径中冲突对数量的最大值为 2。

样例3

输入

4
5 3 4 2
1 2 1

输出

4

说明

设备优先级分别为 $a_1 = 5$、$a_2 = 3$、$a_3 = 4$、$a_4 = 2$，树边为 $(1,2)$、$(2,3)$、$(1,4)$。

考虑路径 $4 \to 1 \to 2 \to 3$，其数列为 $[2, 5, 3, 4]$。

• 顺序对（$i < j$ 且 $a_i < a_j$）有 $(2,5)$、$(2,3)$、$(2,4)$、$(3,4)$，共 4 对。该方向上的逆序对为 $(5,3)$、$(5,4)$，共 2 对。因此这条路径在该方向上的冲突对可按其顺序对计算，为 4。
• 该路径反向为 $3 \to 2 \to 1 \to 4$，数列 $[4, 3, 5, 2]$，逆序对为 $(4,3)$、$(4,2)$、$(3,2)$、$(5,2)$，共 4 对。

无论正向还是反向，该路径的冲突对数量均可达 4，并且这是所有简单路径中的最大值。

样例4

输入

5
2 2 3 1 1
1 2 3 4

输出

6

说明

设备优先级为 $2, 2, 3, 1, 1$，树结构为一条链 $1 - 2 - 3 - 4 - 5$。

关注路径 $1 \to 2 \to 3 \to 4 \to 5$，数列为 $[2, 2, 3, 1, 1]$。

• 该方向的逆序对：前两个 2 与后面两个 1 可形成 $2 \times 2 = 4$ 对，3 与后面两个 1 可形成 $2$ 对，共 6 对。注意相等的值不构成冲突对。
• 顺序对：仅前两个 2 与 3 构成 $2$ 对。

取该方向上的冲突对数量为 6。若考虑路径反向 $[1, 1, 3, 2, 2]$，顺序对有 6 对，同样可达到 6。其余路径均无法超过此值，故最大冲突对数量为 6。