{"problem":{"name":"[CoE R5] X 细胞","description":{"content":"**题意简述** **有根树**为一个有向图，该有向图有一个特殊的顶点，称之为**根**，从根出发，存在唯一的有向路径到达图中的任意其他顶点。按照习惯，一般将有根树中的顶点称为**结点**。**子树**为有根树 $T$ 的一个子图且该子图是一棵以 $T$ 中某个结点为根的有根树。在有根树中，如果有一条边从结点 $i$ 出发，到达结点 $j$，则将结点 $i$ 称为结点 $j$ 的**父结点**，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8581"},"statements":[{"statement_type":"Markdown","content":"**题意简述**\n\n**有根树**为一个有向图，该有向图有一个特殊的顶点，称之为**根**，从根出发，存在唯一的有向路径到达图中的任意其他顶点。按照习惯，一般将有根树中的顶点称为**结点**。**子树**为有根树 $T$ 的一个子图且该子图是一棵以 $T$ 中某个结点为根的有根树。在有根树中，如果有一条边从结点 $i$ 出发，到达结点 $j$，则将结点 $i$ 称为结点 $j$ 的**父结点**，将结点 $j$ 称为结点 $i$ 的**子结点**。将有根树中不存在子结点的结点称为**叶结点**。\n\n给定有根树 $T$，第 $i$ 个结点具有权值 $a_i \\in \\mathbb{Z^+}$ 和 $b_i \\in \\mathbb{Z^+}$。\n\n令 $T'$ 为 $T$ 的一棵子树，$F_i$ 为 $T$ 中所有以结点 $i$ 为根的子树的集合。\n\n- 定义 $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}$。\n\n- 定义 $T_i$ 为一棵以结点 $i$ 为根的子树，$T_i$ 满足 $r(T_i) = \\min \\limits_{T' \\in F_i}r(T')$ 且具有最多的结点数量。\n\n- 定义 $S(T')$：对于 $T$ 中的某个结点 $j$，令其父结点为 $i$，则 $j \\in S(T')$ 当且仅当 $i \\in T'$ 但 $j \\notin T'$ 。\n\n给定一棵具有 $n$ 个结点的有根树 $T$，令根结点为 $i$，对其执行以下操作：\n\n（$1$）将根结点 $i$ 放入结点集合 $Q$，即初始时置 $Q \\leftarrow \\{i\\}$；\n\n（$2$）任取 $Q$ 中的一个元素，令其为 $j$，确定 $T_j$，对于结点 $k \\in S(T_j)$，置 $a_k \\leftarrow a_k + \\lceil r(T_j) \\rceil$；\n\n（$3$）从集合 $Q$ 中删除元素 $j$，并置 $Q \\leftarrow Q \\cup S(T_j)$；\n\n（$4$）若集合 $Q = \\varnothing $，结束操作，否则转步骤（$2$）。\n\n每执行一次步骤（$2$）就会确定一棵 $T$ 的子树，假设在结束操作时一共执行了  $m$ 次步骤（$2$）,令第 $i$ 次执行步骤（$2$）所确定的子树为 $K_i$，最小化以下 $W$ 值：\n\n$$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$$\n\n$\\mathbb{Z^+}$ 表示全体正整数，$\\lceil x \\rceil$ 表示不小于 $x$ 的最小整数。\n\n------------\n\n**原版题面**\n\n$\\text{X}$ 细胞是来自于仙女座星系 $\\text{Gamma}$ 行星的一种古老生命形式。\n\n初始时，只有 $1$ 个 $\\text{X}$ 细胞，而 $\\text{X}$ 细胞可以通过直接分裂来产生后代 $\\text{X}$ 细胞。对于某个 $\\text{X}$ 细胞 $i$ 来说，如果它产生了一个直接后代 $\\text{X}$ 细胞 $j$，则将细胞 $i$ 称为细胞 $j$ 的**母细胞**，将细胞 $j$ 称为 $i$ 的**子细胞**。\n\n注意，母细胞、子细胞的定义不具有传递性。假设细胞 $i$ 产生了一个直接后代细胞 $j$，细胞 $j$ 又产生了一个直接后代细胞 $k$，则将 $j$ 称为 $i$ 的子细胞，$k$ 称为 $j$ 的子细胞，但 $k$ 不是 $i$ 的子细胞。\n\n每个 $\\text{X}$ 细胞具有活力值 $h_x$ 和体积 $v_x$，为了研究的方便，人们为 $\\text{X}$ 细胞定义了**变异指数**\n\n$$d_x = \\frac{h_x}{v_x}$$\n\n该指数用于衡量 $\\text{X}$ 细胞对环境的适应性，变异指数越低，细胞存活的概率越高。\n\n人们发现，当 $\\text{X}$ 细胞受到特定的外界刺激后，它会激活并开始一种被人们称为**同化**的过程来转变为一个 $\\text{Z}$ 细胞。在同化过程开始前，激活的 $\\text{X}$ 细胞会改变自身状态成为一个 $\\text{Y}$ 细胞，$\\text{Y}$ 细胞会不断吸收它的子细胞并进行融合，使得该子细胞成为 $\\text{Y}$ 细胞的一部分。\n\n在融合后，$\\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}$。\n\n在同化过程中，$\\text{Y}$ 细胞会遵循以下原则：\n\n- 如果某个子细胞 $j$ 的母细胞 $i$ 尚未被同化，则该子细胞 $j$ 不会被同化。\n- 能够使得 $\\text{Y}$ 细胞变异指数尽可能地小且同化尽可能多的细胞。\n\n当 $\\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$ 的最小整数）。\n\n需要注意，在同化过程结束时，$\\text{Y}$ 细胞的变异指数要求尽可能地小，但在同化过程中，$\\text{Y}$ 细胞的变异指数并不要求时刻保持最小（参见输入 $\\#1$）。\n\n研究人员需要通过一种专用设备来产生激活 $\\text{X}$ 细胞的特定外界刺激，每次使用该设备都会消耗一定数量的激活剂，消耗的激活剂数量 $c_t$ 使用以下公式进行计算：\n\n$$c_t = t \\times \\lceil d_z \\rceil $$\n\n其中 $t$ 表示使用该设备的次数序号（初始时从 $1$ 开始计数），$d_z$ 表示该次激活最终生成的 $\\text{Z}$ 细胞的变异指数。\n\n由于母细胞会分泌信息素使得子细胞无法被激活，只能选择不存在母细胞或者母细胞已经被同化的 $\\text{X}$ 细胞作为特定外界刺激的对象，以使其激活并开始同化过程。\n\n给定所有 $\\text{X}$ 细胞之间的相互关系及其活力值和体积，鉴于激活剂非常难以制造，现在需要你制定一个最优的 $\\text{X}$ 细胞激活顺序方案，使得所有的 $\\text{X}$ 细胞均转变为 $\\text{Z}$ 细胞且消耗的激活剂数量最少。\n\n你只需要输出该最少值即可。\n\n## Input\n\n输入的第一行是一个整数 $n$，表示 $\\text{X}$ 细胞的数量。\n\n接下来的一行，包含 $n - 1$ 个整数，依次表示编号为 $2 \\sim n$ 的 $\\text{X}$ 细胞的母细胞的编号。\n\n接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的 $\\text{X}$ 细胞的活力值 $h_i$。\n\n再接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的 $\\text{X}$ 细胞的体积 $v_i$。\n\n初始的 $\\text{X}$ 细胞的编号为 $1$。\n\n------------\n\n**题意简述所对应的输入格式**：\n\n输入的第一行是一个整数 $n$，表示有根树结点的数量。\n\n接下来的一行，包含 $n - 1$ 个整数，依次表示编号为 $2 \\sim n$ 的结点的父结点的编号。\n\n接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的结点的权值 $a_i$。\n\n再接下来的一行，包含 $n$ 个整数，依次表示编号为 $i$ 的结点的权值 $b_i$。\n\n根结点的编号为 $1$。\n\n## Output\n\n输出一个整数，表示使得所有 $\\text{X}$ 细胞均转变为 $\\text{Z}$ 细胞所需消耗的激活剂数量的最少值。\n\n------------\n\n**题意简述所对应的输出格式**：\n\n输出一个整数，表示 $W$ 的最小值。\n\n[samples]\n\n## Note\n\n**样例说明**\n\n输入 $\\#1$：\n\n- 激活细胞 $1$，同化细胞 $2、3$，产生的 $\\text{Z}$ 细胞活力值 $h_z = 24$，体积 $v_z = 12$，变异指数 $d_z = \\frac {h_z}{v_z} = \\frac {24}{12} = 2$。\n\n- $1$ 次激活总共最少需要消耗的激活剂数量为 $c_1 = t \\times \\lceil d_z \\rceil = 1 \\times \\lceil \\frac {24}{12} \\rceil = 1 \\times 2 = 2$。\n\n- 初始时 $\\text{Y}$ 细胞的变异指数为 $5$，当同化细胞 $2$ 后，变异指数为 $6$，当同化细胞 $3$ 后，变异指数变为 $2$。由此可见，在同化过程中，$\\text{Y}$ 细胞的变异指数并不是时刻都保持最小，只需在最后停止同化转变为 $\\text{Z}$ 细胞时为最小值即可。\n\n输入 $\\#2$：\n\n- 激活细胞 $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$；\n\n- 激活细胞 $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$。\n\n- $2$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 = 1 + 8 = 9$。\n\n输入 $\\#3$：\n\n- 激活细胞 $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$。\n\n- 激活细胞 $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$。\n\n- 激活细胞 $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$。\n\n- 激活细胞 $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$。\n\n- 激活细胞 $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$。\n\n- $5$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 + c_3 + c_4 + c_5 = 1 + 16 + 84 + 72 + 50 = 223$。\n\n输入 $\\#4$：\n\n- 激活细胞 $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$。\n\n- 激活细胞 $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$。\n\n- 激活细胞 $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$。\n\n- 激活细胞 $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$。\n\n- $4$ 次激活总共最少需要消耗的激活剂数量为 $c_1 + c_2 + c_3 + c_4 = 4 + 42 + 54 + 24 = 124$。\n\n------------\n\n**数据范围**\n\n**本题采用捆绑测试。某些子任务的输入文件较大，请使用合适的输入读取方式。**\n\n| 子任务 | 分值 | $n \\leq$ | 特殊性质 | 时间限制 | 内存限制 | 子任务依赖 |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| $1$ | $10$ | $20$ |   | $1 \\text{ s}$ |  $256 \\text{ MB}$ | |\n| $2$ | $30$ | $10^3$ |   | $1 \\text{ s}$ | $256 \\text{ MB}$ | $1$ |\n| $3$ | $10$ | $10^5$ |   | $1 \\text{ s}$ | $256 \\text{ MB}$ | $1 \\sim 2$ |\n| $4$ | $10$ | $10^6$ | $\\text{A}$ | $3 \\text{ s}$ | $256 \\text{ MB}$ |  |\n| $5$ | $20$ | $10^6$ | $\\text{B}$ | $1 \\text{ s}$ | $320 \\text{ MB}$ |  |\n| $6$ | $10$ | $10^6$ | $\\text{C}$ | $1 \\text{ s}$ | $256 \\text{ MB}$ |  |\n| $7$ | $10$ | $10^6$ |   | $3 \\text{ s}$ | $320 \\text{ MB}$ | $1 \\sim 6$ |\n\n- 特殊性质 $\\text{A}$：即给定的有根树所对应的图是星形图。$\\forall \\  2 \\leq i \\leq n$，$f_i = 1$。\n- 特殊性质 $\\text{B}$：给定的有根树所对应的图是有向链。$\\forall \\ 2 \\leq i \\leq n$，$f_i = i - 1$。\n- 特殊性质 $\\text{C}$：数据随机生成。$\\forall \\ 2 \\leq i \\leq n$，$f_i$ 是 $[1, i - 1]$ 中随机选取的整数。$h_i, v_i$ 是 $[1, 10^6]$ 中随机选取的整数。\n\n对于 $100 \\%$ 的数据，$1 \\leq n \\leq 10^6$，$1 \\leq h_i \\leq 10^6$，$1 \\leq v_i \\leq 10^6$，答案不超过 $10^{18}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8581","tags":["数学","图论","贪心","堆","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3\n1 2\n5 7 12\n1 1 10","2"],["3\n1 1\n2 2 12\n2 3 4","9"],["5\n1 2 2 1\n1 7 10 20 9\n1 1 1 1 1","223"],["12\n1 2 3 1 5 6 7 1 9 10 11\n4 10 2 1 50 1 20 9 40 2 15 10\n1 1 1 1 1 1 1 1 1 1 1 1","124"]],"created_at":"2026-03-03 11:09:25"}}