P8581 [CoE R5] X 细胞

**题意简述** **有根树**为一个有向图，该有向图有一个特殊的顶点，称之为**根**，从根出发，存在唯一的有向路径到达图中的任意其他顶点。按照习惯，一般将有根树中的顶点称为**结点**。**子树**为有根树 $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$ 值： $$W = 1 \times \lceil r(K_1) \rceil + 2 \times \lceil r(K_2) \rceil + \cdots + m \times \lceil r(K_m) \rceil = \sum_{i = 1}^{m}i \times \lceil r(K_i) \rceil$$ $\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}$ 细胞定义了**变异指数** $$d_x = \frac{h_x}{v_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$ 使用以下公式进行计算： $$c_t = t \times \lceil d_z \rceil $$ 其中 $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$ 的最小值。

**样例说明** 输入 $\#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$。 ------------ **数据范围** **本题采用捆绑测试。某些子任务的输入文件较大，请使用合适的输入读取方式。** | 子任务 | 分值 | $n \leq$ | 特殊性质 | 时间限制 | 内存限制 | 子任务依赖 | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $10$ | $20$ | | $1 \text{ s}$ | $256 \text{ MB}$ | | | $2$ | $30$ | $10^3$ | | $1 \text{ s}$ | $256 \text{ MB}$ | $1$ | | $3$ | $10$ | $10^5$ | | $1 \text{ s}$ | $256 \text{ MB}$ | $1 \sim 2$ | | $4$ | $10$ | $10^6$ | $\text{A}$ | $3 \text{ s}$ | $256 \text{ MB}$ | | | $5$ | $20$ | $10^6$ | $\text{B}$ | $1 \text{ s}$ | $320 \text{ MB}$ | | | $6$ | $10$ | $10^6$ | $\text{C}$ | $1 \text{ s}$ | $256 \text{ MB}$ | | | $7$ | $10$ | $10^6$ | | $3 \text{ s}$ | $320 \text{ MB}$ | $1 \sim 6$ | - 特殊性质 $\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}$。