P8581 [CoE R5] X Cell

**Brief statement** A **rooted tree** is a directed graph with a special vertex called the **root**. From the root, there is a unique directed path to every other vertex in the graph. By convention, vertices in a rooted tree are called **nodes**. A **subtree** is a subgraph of a rooted tree $T$ that is itself a rooted tree whose root is some node in $T$. In a rooted tree, if there is an edge from node $i$ to node $j$, then node $i$ is called the **parent** of node $j$, and node $j$ is called a **child** of node $i$. A node with no children is called a **leaf node**. Given a rooted tree $T$, the $i$-th node has weights $a_i \in \mathbb{Z^+}$ and $b_i \in \mathbb{Z^+}$. Let $T'$ be a subtree of $T$, and let $F_i$ be the set of all subtrees of $T$ rooted at node $i$. - Define $r(T') = \frac {a(T')}{b(T')}$, where $a(T') = \sum \limits_{j \in T'}{a_j}$ and $b(T') = \sum \limits_{j \in T'}{b_j}$. - Define $T_i$ to be a subtree rooted at node $i$ such that $r(T_i) = \min \limits_{T' \in F_i}r(T')$, and among those, it has the maximum number of nodes. - Define $S(T')$: for a node $j$ in $T$, let its parent be $i$. Then $j \in S(T')$ if and only if $i \in T'$ but $j \notin T'$. Given a rooted tree $T$ with $n$ nodes, let the root be $i$, and perform the following operations: ($1$) Put the root node $i$ into a node set $Q$, i.e., initially set $Q \leftarrow \{i\}$. ($2$) Choose any element in $Q$ and let it be $j$. Determine $T_j$. For each node $k \in S(T_j)$, set $a_k \leftarrow a_k + \lceil r(T_j) \rceil$. ($3$) Remove $j$ from $Q$, and set $Q \leftarrow Q \cup S(T_j)$. ($4$) If $Q = \varnothing$, stop; otherwise go to step ($2$). Each execution of step ($2$) determines a subtree of $T$. Suppose step ($2$) is executed a total of $m$ times when the process ends. Let the subtree determined in the $i$-th execution of step ($2$) be $K_i$. Minimize the following value $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^+}$ denotes the set of all positive integers, and $\lceil x \rceil$ denotes the smallest integer not less than $x$. ------------ **Original statement** $\text{X}$ cells are an ancient life form from planet $\text{Gamma}$ in the Andromeda galaxy. Initially, there is only $1$ $\text{X}$ cell, and $\text{X}$ cells can produce descendant $\text{X}$ cells by direct division. For an $\text{X}$ cell $i$, if it produces a direct descendant $\text{X}$ cell $j$, then cell $i$ is called the **mother cell** of cell $j$, and cell $j$ is called a **child cell** of $i$. Note that the definitions of mother cell and child cell are not transitive. Suppose cell $i$ produces a direct descendant cell $j$, and cell $j$ produces a direct descendant cell $k$. Then $j$ is a child cell of $i$, and $k$ is a child cell of $j$, but $k$ is not a child cell of $i$. Each $\text{X}$ cell has a vitality value $h_x$ and a volume $v_x$. For convenience, people define a **mutation index** for $\text{X}$ cells: $$d_x = \frac{h_x}{v_x}$$ This index measures how well an $\text{X}$ cell adapts to the environment. The lower the mutation index, the higher the probability that the cell survives. It has been found that when an $\text{X}$ cell receives a certain specific external stimulus, it will activate and begin a process called **assimilation** to transform into a $\text{Z}$ cell. Before assimilation starts, the activated $\text{X}$ cell changes its state into a $\text{Y}$ cell. The $\text{Y}$ cell continuously absorbs its child cells and fuses with them, making the child cell become part of the $\text{Y}$ cell. After fusion, the vitality value and volume of the $\text{Y}$ cell become the sums of those before fusion. That is, suppose $n$ cells fuse into one $\text{Y}$ cell, and these $n$ cells have vitality values and volumes $h_1$, $h_2$, …, $h_n$ and $v_1$, $v_2$, …, $v_n$ respectively. After fusion, the $\text{Y}$ cell has vitality value $h_y = \sum_{i=1}^{n}h_i$, volume $v_y = \sum_{i=1}^{n}v_i$, and mutation index $d_y = \frac{h_y}{v_y}$. During assimilation, the $\text{Y}$ cell follows these rules: - If a child cell $j$ has a mother cell $i$ that has not yet been assimilated, then the child cell $j$ will not be assimilated. - Make the mutation index of the $\text{Y}$ cell as small as possible, and assimilate as many cells as possible. When the $\text{Y}$ cell can no longer assimilate more cells, it stops assimilating, transforms into a $\text{Z}$ cell, and releases pheromones (the vitality value and volume do not change before and after the state change). The pheromone has the following effect: let the mutation index of the resulting $\text{Z}$ cell be $d_z = \frac{h_z}{v_z}$. If an unassimilated child cell $j$ has a mother cell $i$ that is assimilated by this $\text{Z}$ cell, then the vitality value $h_j$ of cell $j$ increases by $\lceil d_z \rceil$ ($\lceil x \rceil$ denotes the smallest integer not less than $x$). Note that when the assimilation process ends, the mutation index of the $\text{Y}$ cell is required to be as small as possible, but during the assimilation process, the mutation index of the $\text{Y}$ cell does not need to remain minimal at all times (see input $\#1$). Researchers need to use a special device to produce the specific external stimulus that activates $\text{X}$ cells. Each use of the device consumes a certain amount of activator. The amount of activator consumed $c_t$ is computed by: $$c_t = t \times \lceil d_z \rceil $$ where $t$ is the usage index of the device (starting from $1$), and $d_z$ is the mutation index of the $\text{Z}$ cell finally produced by this activation. Because mother cells secrete pheromones that prevent child cells from being activated, one can only choose an $\text{X}$ cell that has no mother cell, or whose mother cell has already been assimilated, as the target of the specific external stimulus, so that it activates and begins assimilation. Given the relationships among all $\text{X}$ cells and their vitality values and volumes, and since activators are very hard to produce, you now need to design an optimal activation order plan for $\text{X}$ cells so that all $\text{X}$ cells transform into $\text{Z}$ cells while the total activator consumption is minimized. You only need to output this minimum value.

The first line contains an integer $n$, representing the number of $\text{X}$ cells. The next line contains $n - 1$ integers, in order representing the mother cell index of $\text{X}$ cells numbered $2 \sim n$. The next line contains $n$ integers, in order representing the vitality value $h_i$ of the $\text{X}$ cell numbered $i$. The next line contains $n$ integers, in order representing the volume $v_i$ of the $\text{X}$ cell numbered $i$. The initial $\text{X}$ cell is numbered $1$. ------------ **Input format corresponding to the brief statement**: The first line contains an integer $n$, representing the number of nodes in the rooted tree. The next line contains $n - 1$ integers, in order representing the parent index of nodes numbered $2 \sim n$. The next line contains $n$ integers, in order representing the weight $a_i$ of the node numbered $i$. The next line contains $n$ integers, in order representing the weight $b_i$ of the node numbered $i$. The root node is numbered $1$.

Output one integer, representing the minimum total activator consumption needed to make all $\text{X}$ cells transform into $\text{Z}$ cells. ------------ **Output format corresponding to the brief statement**: Output one integer, representing the minimum value of $W$.

**Sample explanation** Input $\#1$: - Activate cell $1$, assimilate cells $2$ and $3$. The resulting $\text{Z}$ cell has vitality value $h_z = 24$, volume $v_z = 12$, and mutation index $d_z = \frac {h_z}{v_z} = \frac {24}{12} = 2$. - The minimum activator consumption for the $1$-st activation is $c_1 = t \times \lceil d_z \rceil = 1 \times \lceil \frac {24}{12} \rceil = 1 \times 2 = 2$. - Initially, the $\text{Y}$ cell’s mutation index is $5$. After assimilating cell $2$, the mutation index is $6$. After assimilating cell $3$, the mutation index becomes $2$. This shows that during assimilation, the $\text{Y}$ cell’s mutation index does not need to stay minimal at all times; it only needs to be minimal when it finally stops assimilating and transforms into a $\text{Z}$ cell. Input $\#2$: - Activate cell $1$, assimilate cell $2$. The resulting $\text{Z}$ cell has vitality value $h_z = 2 + 2 = 4$, volume $v_z = 2 + 3 = 5$, mutation index $d_z = \frac {h_z}{v_z} = \frac {4}{5}$. The activator consumption for this activation is $c_1 = t \times \lceil d_z \rceil= 1 \times \lceil \frac {4}{5} \rceil = 1 \times 1 = 1$. This $\text{Z}$ cell releases pheromones that increase the vitality value of cell $3$ by $1$, so the vitality value of cell $3$ becomes $13$. - Activate cell $3$, assimilate no other cells. The resulting $\text{Z}$ cell has vitality value $h_z = 13$, volume $v_z = 4$, mutation index $d_z = \frac {h_z}{v_z} = \frac {13}{4}$. The activator consumption for this activation is $c_2 = t \times \lceil d_z \rceil = 2 \times \lceil \frac {13}{4} \rceil= 2 \times 4 = 8$. - The minimum total activator consumption for $2$ activations is $c_1 + c_2 = 1 + 8 = 9$. Input $\#3$: - Activate cell $1$, assimilate no other cells. The resulting $\text{Z}$ cell has vitality value $h_z = 1$, volume $v_z = 1$, mutation index $d_z = \frac {h_z}{v_z} = \frac {1}{1} = 1$. The total activator consumption is $c_1 = t \times \lceil d_z \rceil = 1 \times \lceil 1 \rceil = 1$. The $\text{Z}$ cell releases pheromones, increasing the vitality values of cells $2$ and $5$ by $1$ each, so their current vitality values are $8$ and $10$. - Activate cell $2$, assimilate no other cells. The resulting $\text{Z}$ cell has vitality value $h_z = 8$, volume $v_z = 1$, mutation index $d_z = \frac {h_z}{v_z} = \frac {8}{1} = 8$. The total activator consumption is $c_2 = t \times \lceil d_z \rceil = 2 \times \lceil 8 \rceil = 16$. The $\text{Z}$ cell releases pheromones, increasing the vitality values of cells $3$ and $4$ by $8$ each, so their current vitality values are $18$ and $28$. - Activate cell $4$, assimilate no other cells. The resulting $\text{Z}$ cell has vitality value $h_z = 28$, volume $v_z = 1$, mutation index $d_z = \frac {h_z}{v_z} = \frac {28}{1} = 28$. The total activator consumption is $c_3 = t \times \lceil d_z \rceil = 3 \times \lceil 28 \rceil = 84$. - Activate cell $3$, assimilate no other cells. The resulting $\text{Z}$ cell has vitality value $h_z = 18$, volume $v_z = 1$, mutation index $d_z = \frac {h_z}{v_z} = \frac {18}{1} = 18$. The total activator consumption is $c_4 = t \times \lceil d_z \rceil = 4 \times \lceil 18 \rceil = 72$. - Activate cell $5$, assimilate no other cells. The resulting $\text{Z}$ cell has vitality value $h_z = 10$, volume $v_z = 1$, mutation index $d_z = \frac {h_z}{v_z} = \frac {10}{1} = 10$. The total activator consumption is $c_5 = t \times \lceil d_z \rceil = 5 \times \lceil 10 \rceil = 50$. - The minimum total activator consumption for $5$ activations is $c_1 + c_2 + c_3 + c_4 + c_5 = 1 + 16 + 84 + 72 + 50 = 223$. Input $\#4$: - Activate cell $1$, assimilate no other cells. The resulting $\text{Z}$ cell has mutation index $d_z = \frac {h_z}{v_z} = \frac {4}{1}$. It releases pheromones that increase the vitality values of cells $2$, $5$, and $9$ by $4$. The activator consumption is $c_1 = 1 \times \lceil \frac {4}{1} \rceil = 1 \times 4 = 4$. - Activate cell $5$, assimilate cells $6$, $7$, and $8$. The resulting $\text{Z}$ cell has mutation index $d_z = \frac {h_z}{v_z} = \frac {84}{4}$. The activator consumption is $c_2 = 2 \times \lceil \frac {84}{4} \rceil = 2 \times 21 = 42$. - Activate cell $9$, assimilate cells $10$, $11$, and $12$. The resulting $\text{Z}$ cell has mutation index $d_z = \frac {h_z}{v_z} = \frac {71}{4}$. The activator consumption is $c_3 = 3 \times \lceil \frac {71}{4} \rceil = 3 \times 18 = 54$. - Activate cell $2$, assimilate cells $3$ and $4$. The resulting $\text{Z}$ cell has mutation index $d_z = \frac {h_z}{v_z} = \frac {17}{3}$. The activator consumption is $c_4 = 4 \times \lceil \frac {17}{3} \rceil = 4 \times 6 = 24$. - The minimum total activator consumption for $4$ activations is $c_1 + c_2 + c_3 + c_4 = 4 + 42 + 54 + 24 = 124$. ------------ **Constraints** **This problem uses bundled testdata. Some subtask input files are large, so please use an appropriate input method.** | Subtask | Points | $n \leq$ | Special Property | Time Limit | Memory Limit | Dependencies | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | $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$ | - Special property $\text{A}$: the rooted tree corresponds to a star graph. $\forall \ 2 \leq i \leq n$, $f_i = 1$. - Special property $\text{B}$: the rooted tree corresponds to a directed chain. $\forall \ 2 \leq i \leq n$, $f_i = i - 1$. - Special property $\text{C}$: the data is randomly generated. $\forall \ 2 \leq i \leq n$, $f_i$ is a random integer chosen from $[1, i - 1]$. $h_i, v_i$ are random integers chosen from $[1, 10^6]$. For $100\%$ of the data, $1 \leq n \leq 10^6$, $1 \leq h_i \leq 10^6$, $1 \leq v_i \leq 10^6$, and the answer does not exceed $10^{18}$. Translated by ChatGPT 5