U213281 [GDOI2022 普及组] 流水线

在计算机组成原理这门课中，小明的老师布置了实现 $\rm CPU$ 流水线的作业。小明打算设计出一个效率最高的流水线，简单来说，流水线就是将 $\rm CPU$ 分成若干个任务模块，而一个模块又可以继续分成更小的模块，小模块可以划分成更小的小小模块……根据常识我们知道把一个任务划分后，每一个部分的代价会变少，但是可能会产生额外的代价。所以小明希望你帮助他解决这个问题。 我们可以用一棵以 $1$ 为根的有根树来描述模块之间的关系，每个节点是一个模块，每个节点的点权对应着该模块的时间代价。每一个非叶子节点可以划分成该节点的儿子节点对应的模块。 每个模块都有一定的时间代价，而流水线最后的效率我们可以用划分的模块数乘上模块中时间最大的一个来表示，时间代价越小，流水线的效率越高。也就是说，假如小明最后把 $\rm CPU$ 划分成了 $m$ 个模块，每个模块的代价为 $w_1,w_2,\cdots,w_m$，则总代价为 $m\cdot \max(w_1,w_2,\cdots,w_m)$。另外，我们认为根节点对应的模块不往下划分模块也是一种合法的方案。 请你帮小明找到效率最高的流水线设计方案吧。

第一行一个正整数 $n$，表示模块对应有根树的节点个数。 第二行 $n$ 个整数，表示 $n$ 个模块的时间代价 $w_i$。 第三行 $n-1$ 个整数 $f_i$（$2\leq i\leq n$），表示节点 $2,\cdots,n$ 在有根树中的父节点。保证给出的是一棵以 $1$ 为根的树。

一个整数 $T$，表示最小的时间代价。

#### 样例解释 样例中将模块 $1$ 拆分为模块 $2$ 和模块 $3$，再将模块 $2$ 拆分成模块 $4$ 和模块 $5$，代价为 $3\cdot 3=9$。 #### 数据范围 对于所有测试点，$1\leq n\leq 10^5$，$0\leq w_i\leq 10^9$，$w_i\leq w_{f_i}$。 对于 $20\%$ 的数据，$n\leq 20$，$w_i\leq 10^9$； 对于 $20\%$ 的数据，$n\leq 500$，$w_i\leq 10^9$； 对于 $30\%$ 的数据，$n\leq 10^5$，$w_i\leq 100$； 对于 $30\%$ 的数据，$n\leq 10^5$，$w_i\leq 10^9$；