题目描述

在雪白帝国背部分布有$N$个城市，从$1$到$N$编号。对于一座城市$i$，有$A_i$位居民居住在其中。

它们间分布有$N-1$条道路，从$2$到$N$编号。对于一条路$j$，它连接城市$j$和$P_j$，其中$P_j \lt j$。任何城市最多被连接到36条路。

在冬季，危险的驾驶条件使得政府执行交通管制，所有的路都变为单向高速公路，即对于一条路$j$，它要么成为从城市$j$到城市$P_j$的单向高速公路，要么成为从城市$P_j$到城市$j$的单向高速公路。

此时，每个居民都想给其他所有公民寄假日贺卡。然而，如果要从城市$X$向城市$Y$发送一张假日贺卡，必须保证可以通过高速公路连接$X$和$Y$，或者$X=Y$。

请求出，当所有的公路都被转换为单向高速公路后，最多可以被送出的贺卡总数。

输入格式

第一行，一个正整数$N$。

第二行，$N$个正整数$A_1$ ~ $A_N$。

第三行，$N-1$个正整数$P_2$ ~ $P_N$。

输出格式

一行，一个正整数，即最多可以被送出的贺卡总数。

4
3 3 4 1
1 2 1

67

提示

样例解释

一种可能的做法是将：

转化为：

此时，3号城的每个居民都可以往3号城寄3张卡片，往2号城寄3张，往1号城寄3张，往4号城寄1张。所以3号城共计可以发送40张。

相似地，2号城共可寄18张，3号城共可寄9张，4号城一张也寄不了。

所以答案为$40+18+9+0=67$。

限制

$2 \le N \le 200 000$

对于任意合法$i$，$1 \le A_i \le 10 000$

对于任意合法$j$，$1 \le P_j \le j$

设$D$为任意一个城市连接的道路数量。$D \le 36$。

子任务

Subtask 1（20分）：$N \le 10$

Subtask 2（20分）：$N \le 1000$，$D \le 10$

Subtask 3（20分）：$D \le 18$

Subtask 4（20分）：$N=37$，且所有的道路均连向一个城市，亦即这个城市有36条连接的城市，且它们均只通过一条道路连向此城。

Subtask 5（20分）：没有附加限制。