题目描述

题意简述

有根树为一个有向图，该有向图有一个特殊的顶点，称之为根，从根出发，存在唯一的有向路径到达图中的任意其他顶点。按照习惯，一般将有根树中的顶点称为结点。子树为有根树 $T$ 的一个子图且该子图是一棵以 $T$ 中某个结点为根的有根树。在有根树中，如果有一条边从结点 $i$ 出发，到达结点 $j$，则将结点 $i$ 称为结点 $j$ 的父结点，将结点 $j$ 称为结点 $i$ 的子结点。将有根树中不存在子结点的结点称为叶结点。

给定有根树 $T$，第 $i$ 个结点具有权值 $a_i \in \mathbb{Z^+}$ 和 $b_i \in \mathbb{Z^+}$。

令 $T'$ 为 $T$ 的一棵子树，$F_i$ 为 $T$ 中所有以结点 $i$ 为根的子树的集合。

• 定义 $r(T') = \frac {a(T')}{b(T')}$，其中 $a(T') = \sum \limits_{j \in T'}{a_j}$，$b(T') = \sum \limits_{j \in T'}{b_j}$。

• 定义 $T_i$ 为一棵以结点 $i$ 为根的子树，$T_i$ 满足 $r(T_i) = \min \limits_{T' \in F_i}r(T')$ 且具有最多的结点数量。

• 定义 $S(T')$：对于 $T$ 中的某个结点 $j$，令其父结点为 $i$，则 $j \in S(T')$ 当且仅当 $i \in T'$ 但 $j \notin T'$ 。

给定一棵具有 $n$ 个结点的有根树 $T$，令根结点为 $i$，对其执行以下操作：

（$1$）将根结点 $i$ 放入结点集合 $Q$，即初始时置 $Q \leftarrow \{i\}$；

（$2$）任取 $Q$ 中的一个元素，令其为 $j$，确定 $T_j$，对于结点 $k \in S(T_j)$，置 $a_k \leftarrow a_k + \lceil r(T_j) \rceil$；

（$3$）从集合 $Q$ 中删除元素 $j$，并置 $Q \leftarrow Q \cup S(T_j)$；

（$4$）若集合 $Q = \varnothing$，结束操作，否则转步骤（$2$）。

每执行一次步骤（$2$）就会确定一棵 $T$ 的子树，假设在结束操作时一共执行了 $m$ 次步骤（$2$）,令第 $i$ 次执行步骤（$2$）所确定的子树为 $K_i$，最小化以下 $W$ 值：

$\mathbb{Z^+}$ 表示全体正整数，$\lceil x \rceil$ 表示不小于 $x$ 的最小整数。

原版题面

$\text{X}$ 细胞是来自于仙女座星系 $\text{Gamma}$ 行星的一种古老生命形式。

初始时，只有 $1$ 个 $\text{X}$ 细胞，而 $\text{X}$ 细胞可以通过直接分裂来产生后代 $\text{X}$ 细胞。对于某个 $\text{X}$ 细胞 $i$ 来说，如果它产生了一个直接后代 $\text{X}$ 细胞 $j$，则将细胞 $i$ 称为细胞 $j$ 的母细胞，将细胞 $j$ 称为 $i$ 的子细胞。

注意，母细胞、子细胞的定义不具有传递性。假设细胞 $i$ 产生了一个直接后代细胞 $j$，细胞 $j$ 又产生了一个直接后代细胞 $k$，则将 $j$ 称为 $i$ 的子细胞，$k$ 称为 $j$ 的子细胞，但 $k$ 不是 $i$ 的子细胞。

每个 $\text{X}$ 细胞具有活力值 $h_x$ 和体积 $v_x$，为了研究的方便，人们为 $\text{X}$ 细胞定义了变异指数

该指数用于衡量 $\text{X}$ 细胞对环境的适应性，变异指数越低，细胞存活的概率越高。

人们发现，当 $\text{X}$ 细胞受到特定的外界刺激后，它会激活并开始一种被人们称为同化的过程来转变为一个 $\text{Z}$ 细胞。在同化过程开始前，激活的 $\text{X}$ 细胞会改变自身状态成为一个 $\text{Y}$ 细胞，$\text{Y}$ 细胞会不断吸收它的子细胞并进行融合，使得该子细胞成为 $\text{Y}$ 细胞的一部分。

在融合后，$\text{Y}$ 细胞的活力值和体积为融合前的细胞活力值和体积的加和。也就是说，假设有 $n$ 个细胞经过融合成为一个 $\text{Y}$ 细胞，这 $n$ 个细胞的活力值和体积分别为 $h_1$，$h_2$，…，$h_n$ 和 $v_1$，$v_2$，…，$v_n$，则融合完成后，该 $\text{Y}$ 细胞的活力值 $h_y = \sum_{i=1}^{n}h_i$，体积 $v_y = \sum_{i=1}^{n}v_i$，变异指数 $d_y = \frac{h_y}{v_y}$。

在同化过程中，$\text{Y}$ 细胞会遵循以下原则：

• 如果某个子细胞 $j$ 的母细胞 $i$ 尚未被同化，则该子细胞 $j$ 不会被同化。
• 能够使得 $\text{Y}$ 细胞变异指数尽可能地小且同化尽可能多的细胞。

当 $\text{Y}$ 细胞无法再同化更多的细胞时，它会停止同化过程，转变为一个 $\text{Z}$ 细胞并释放信息素（状态转变前后，细胞的活力值和体积不变）。该信息素会产生以下作用：令生成的 $\text{Z}$ 细胞的变异指数为 $d_z = \frac{h_z}{v_z}$，如果某个尚未被同化的子细胞 $j$ 的母细胞 $i$ 被该 $\text{Z}$ 细胞同化，则该子细胞 $j$ 的活力值 $h_j$ 增加 $\lceil d_z \rceil$（$\lceil x \rceil$ 表示不小于 $x$ 的最小整数）。

需要注意，在同化过程结束时，$\text{Y}$ 细胞的变异指数要求尽可能地小，但在同化过程中，$\text{Y}$ 细胞的变异指数并不要求时刻保持最小（参见输入 $\#1$）。

研究人员需要通过一种专用设备来产生激活 $\text{X}$ 细胞的特定外界刺激，每次使用该设备都会消耗一定数量的激活剂，消耗的激活剂数量 $c_t$ 使用以下公式进行计算：

其中 $t$ 表示使用该设备的次数序号（初始时从 $1$ 开始计数），$d_z$ 表示该次激活最终生成的 $\text{Z}$ 细胞的变异指数。

由于母细胞会分泌信息素使得子细胞无法被激活，只能选择不存在母细胞或者母细胞已经被同化的 $\text{X}$ 细胞作为特定外界刺激的对象，以使其激活并开始同化过程。

给定所有 $\text{X}$ 细胞之间的相互关系及其活力值和体积，鉴于激活剂非常难以制造，现在需要你制定一个最优的 $\text{X}$ 细胞激活顺序方案，使得所有的 $\text{X}$ 细胞均转变为 $\text{Z}$ 细胞且消耗的激活剂数量最少。

你只需要输出该最少值即可。

输入格式

输入的第一行是一个整数 $n$，表示 $\text{X}$ 细胞的数量。

接下来的一行，包含 $n - 1$ 个整数，依次表示编号为 $2 \sim n$ 的 $\text{X}$ 细胞的母细胞的编号。

接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的 $\text{X}$ 细胞的活力值 $h_i$。

再接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的 $\text{X}$ 细胞的体积 $v_i$。

初始的 $\text{X}$ 细胞的编号为 $1$。

题意简述所对应的输入格式：

输入的第一行是一个整数 $n$，表示有根树结点的数量。

接下来的一行，包含 $n - 1$ 个整数，依次表示编号为 $2 \sim n$ 的结点的父结点的编号。

接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的结点的权值 $a_i$。

再接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的结点的权值 $b_i$。

根结点的编号为 $1$。

输出格式

输出一个整数，表示使得所有 $\text{X}$ 细胞均转变为 $\text{Z}$ 细胞所需消耗的激活剂数量的最少值。

题意简述所对应的输出格式：

输出一个整数，表示 $W$ 的最小值。

3
1 2
5 7 12
1 1 10

2

3
1 1
2 2 12
2 3 4

9

5
1 2 2 1
1 7 10 20 9
1 1 1 1 1

223

12
1 2 3 1 5 6 7 1 9 10 11
4 10 2 1 50 1 20 9 40 2 15 10
1 1 1 1 1 1 1 1 1 1 1 1

124

提示

样例说明

输入 $\#1$：

• 激活细胞 $1$，同化细胞 $2、3$，产生的 $\text{Z}$ 细胞活力值 $h_z = 24$，体积 $v_z = 12$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {24}{12} = 2$。

• $1$ 次激活总共最少需要消耗的激活剂数量为 $c_1 = t \times \lceil d_z \rceil = 1 \times \lceil \frac {24}{12} \rceil = 1 \times 2 = 2$。

• 初始时 $\text{Y}$ 细胞的变异指数为 $5$，当同化细胞 $2$ 后，变异指数为 $6$，当同化细胞 $3$ 后，变异指数变为 $2$。由此可见，在同化过程中，$\text{Y}$ 细胞的变异指数并不是时刻都保持最小，只需在最后停止同化转变为 $\text{Z}$ 细胞时为最小值即可。

输入 $\#2$：

• 激活细胞 $1$，同化细胞 $2$，产生的 $\text{Z}$ 细胞活力值 $h_z = 2 + 2 = 4$，体积 $v_z = 2 + 3 = 5$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {4}{5}$，该次激活消耗的激活剂数量 $c_1 = t \times \lceil d_z \rceil= 1 \times \lceil \frac {4}{5} \rceil = 1 \times 1 = 1$，该 $\text{Z}$ 细胞释放信息素使得细胞 $3$ 的活力值增加 $1$，则细胞 $3$ 的活力值变为 $13$；

• 激活细胞 $3$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 13$，体积 $v_z = 4$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {13}{4}$，该次激活消耗的激活剂数量 $c_2 = t \times \lceil d_z \rceil = 2 \times \lceil \frac {13}{4} \rceil= 2 \times 4 = 8$。

• $2$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 = 1 + 8 = 9$。

输入 $\#3$：

• 激活细胞 $1$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 1$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {1}{1} = 1$。总共消耗的激活剂数量 $c_1 = t \times \lceil d_z \rceil = 1 \times \lceil 1 \rceil = 1$。$\text{Z}$ 细胞释放信息素，使得细胞 $2$、$5$ 的活力值各增加 $1$，细胞 $2$、$5$ 的活力值当前为 $8$、$10$。

• 激活细胞 $2$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 8$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {8}{1} = 8$。总共消耗的激活剂数量 $c_2 = t \times \lceil d_z \rceil = 2 \times \lceil 8 \rceil = 16$。$\text{Z}$ 细胞释放信息素，使得细胞 $3$、$4$ 的活力值各增加 $8$，细胞 $3$、$4$ 的活力值当前为 $18$、$28$。

• 激活细胞 $4$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 28$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {28}{1} = 28$。总共消耗的激活剂数量 $c_3 = t \times \lceil d_z \rceil = 3 \times \lceil 28 \rceil = 84$。

• 激活细胞 $3$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 18$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {18}{1} = 18$。总共消耗的激活剂数量 $c_4 = t \times \lceil d_z \rceil = 4 \times \lceil 18 \rceil = 72$。

• 激活细胞 $5$，未同化其他细胞，产生的 $\text{Z}$ 细胞活力值 $h_z = 10$，体积 $v_z = 1$，变异指数 $d_z = \frac {h_z}{v_z} = \frac {10}{1} = 10$。总共消耗的激活剂数量 $c_5 = t \times \lceil d_z \rceil = 5 \times \lceil 10 \rceil = 50$。

• $5$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 + c_3 + c_4 + c_5 = 1 + 16 + 84 + 72 + 50 = 223$。

输入 $\#4$：

• 激活细胞 $1$，未同化其他细胞，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {4}{1}$，释放信息素使得细胞 $2、5、9$ 的活力值增加 $4$，消耗激活剂 $c_1 = 1 \times \lceil \frac {4}{1} \rceil = 1 \times 4 = 4$。

• 激活细胞 $5$，同化细胞 $6、7、8$，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {84}{4}$，消耗激活剂 $c_2 = 2 \times \lceil \frac {84}{4} \rceil = 2 \times 21 = 42$。

• 激活细胞 $9$，同化细胞 $10、11、12$，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {71}{4}$，消耗激活剂 $c_3 = 3 \times \lceil \frac {71}{4} \rceil = 3 \times 18 = 54$。

• 激活细胞 $2$，同化细胞 $3、4$，产生的 $\text{Z}$ 细胞变异指数 $d_z = \frac {h_z}{v_z} = \frac {17}{3}$，消耗激活剂 $c_4 = 4 \times \lceil \frac {17}{3} \rceil = 4 \times 6 = 24$。

• $4$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 + c_3 + c_4 = 4 + 42 + 54 + 24 = 124$。

数据范围

本题采用捆绑测试。某些子任务的输入文件较大，请使用合适的输入读取方式。

• 特殊性质 $\text{A}$：即给定的有根树所对应的图是星形图。$\forall \ 2 \leq i \leq n$，$f_i = 1$。
• 特殊性质 $\text{B}$：给定的有根树所对应的图是有向链。$\forall \ 2 \leq i \leq n$，$f_i = i - 1$。
• 特殊性质 $\text{C}$：数据随机生成。$\forall \ 2 \leq i \leq n$，$f_i$ 是 $[1, i - 1]$ 中随机选取的整数。$h_i, v_i$ 是 $[1, 10^6]$ 中随机选取的整数。

对于 $100 \%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq h_i \leq 10^6$，$1 \leq v_i \leq 10^6$，答案不超过 $10^{18}$。