题目描述

译自 CCO 2019 Day1 T3「Winter Driving」。

在冰天雪地的北极地区，散落着编号为 $1$ 到 $N$ 的 $N$ 个城市。每个城市里都住着一些居民，第 $i$ 个城市的人口有 $A_i$ 人。这些城市之间总共有 $N-1$ 条道路，编号为 $2$ 到 $N$。第 $j$ 条道路连接着编号为 $j$ 的城市和编号为 $P_j$ 的城市，满足 $P_j$ 永远小于 $j$ （也就是说道路都是单向的，从编号较大的城市通向编号较小的城市）。需要注意的是，任何一个城市最多只能连接 $36$ 条道路。

北极的冬天来啦！为了安全起见，所有道路都变成了只能单向通行的高速公路。也就是说，第 $j$ 条道路现在只能从城市 $j$ 开往城市 $P_j$，或者只能从城市 $P_j$ 开回城市 $j$，不能两边都通行。

现在，每个居民都想给其他城市的所有居民寄送一张节日明信片。居民 $x$ 可以给居民 $y$ 寄明信片的前提是，$x$ 所在的城市能够通过这些高速公路到达 $y$ 所在的城市。

问题来了，在所有道路都变成高速公路之后，最多可以寄出多少张节日明信片呢？

输入格式

第一行包含一个正整数 $N$，表示城市的数量。

第二行包含 $N$ 个用空格隔开的正整数 $A_1, A_2, \ldots , A_N$，依次表示每个城市的人口数量。

第三行包含 $N-1$ 个用空格隔开的正整数 $P_2, P_3, \ldots , P_N$，依次表示每条道路连接的较小编号的城市。

输出格式

输出一行，包含一个正整数，表示所有道路变成高速公路之后最多可以寄出的明信片总数。

4
3 3 4 1
1 2 1

67

一种将道路变成高速公路的方法是：将第 $2$ 条路变成从城市 $2$ 到城市 $1$ 的单向路，将第 $3$ 条路变成从城市 $3$ 到城市 $2$ 的单向路，将第 $4$ 条路变成从城市 $1$ 到城市 $4$ 的单向路。

如下图所示，圆圈表示城市，数字表示该城市的人口数量。第一幅图展示了道路的初始状态，第二幅图展示了所有道路变成高速公路之后的情况。

城市 $3$ 的每个居民可以向城市 $3$ 的居民发送 $3$ 张明信片，向城市 $2$ 的居民发送 $3$ 张明信片，向城市 $1$ 的居民发送 $3$ 张明信片，向城市 $4$ 的居民发送 $1$ 张明信片，总共可以从城市 $3$ 寄出 $40$ 张明信片。

类似地，其他城市的居民也可以寄出明信片：

• 城市 $2$ 的居民每人可以寄 $6$ 张，共计 $18$ 张。
• 城市 $1$ 的居民每人可以寄 $3$ 张，共计 $9$ 张。
• 城市 $4$ 的居民无法寄出任何明信片。

因此，总共可以寄出的明信片数量为 $40 + 18 + 9 = 67$ 张。

数据范围与提示

对于 $20\%$ 的数据，$N \leq 10$；
对于另外的 $20\%$ 的数据，$N \leq 1000,D \leq 10$；
对于另外的 $20\%$ 的数据，$D \leq 18$；
对于另外的 $20\%$ 的数据，总共有 $37$ 个城市，其中 $1$ 个城市连接了其他 $36$ 个城市，其余 $36$ 个城市只连接了这 $1$ 个城市；
对于 $100\%$ 的数据，$2 \leq N \leq 2\times 10^5$，$1 \leq A_i \leq 10000$，$1 \leq P_j \leq j$。我们将任何一个城市连接的道路数量记为 $D$。题目保证 $D \leq 36$。