Problem Description

Problem Simplification

A rooted tree is a directed graph with a special vertex called the root. From the root, there exists a unique directed path to any other vertex in the graph. By convention, vertices in a rooted tree are referred to as nodes. A subtree of a rooted tree \( T \) is a subgraph of \( T \) that is itself a rooted tree with a node in \( T \) as its root. In a rooted tree, if there is an edge from node \( i \) to node \( j \), then node \( i \) is called the parent node of node \( j \), and node \( j \) is called the child node of node \( i \). Nodes in a rooted tree that have no child nodes are called leaf nodes.

Given a rooted tree \( T \), each node \( i \) has weights \( a_i \in \mathbb{Z}^+ \) and \( b_i \in \mathbb{Z}^+ \).

Let \( T' \) be a subtree of \( T \), and \( 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_{j \in T'} a_j \) and \( b(T') = \sum_{j \in T'} b_j \).
• Define \( T_i \) as a subtree rooted at node \( i \) such that \( r(T_i) = \min_{T' \in F_i} r(T') \) and has the maximum number of nodes.
• Define \( S(T') \): For a node \( j \) in \( T \) with parent node \( i \), \( j \in S(T') \) if and only if \( i \in T' \) but \( j \notin T' \).

Given a rooted tree \( T \) with \( n \) nodes, with the root node being \( i \), perform the following operations:

1. Place the root node \( i \) into the node set \( Q \), i.e., initialize \( Q \leftarrow \{i\} \).
2. Select an element \( j \) from \( Q \), determine \( T_j \), and for each node \( k \in S(T_j) \), set \( a_k \leftarrow a_k + \lceil r(T_j) \rceil \).
3. Remove element \( j \) from set \( Q \), and set \( Q \leftarrow Q \cup S(T_j) \).
4. If \( Q = \varnothing \), end the operation; otherwise, repeat step 2.

Each execution of step 2 determines a subtree of \( T \). Suppose step 2 is executed \( m \) times at the end of the operation. Let the subtree determined in the \( i \)-th execution of step 2 be \( K_i \). Minimize the following \( W \) value:

\[ 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 \]

where \( \mathbb{Z}^+ \) denotes all positive integers, and \( \lceil x \rceil \) denotes the smallest integer not less than \( x \).

Input Format

The first line of input is an integer \( n \), the number of nodes in the rooted tree.

The next line contains \( n - 1 \) integers, representing the parent node's index for nodes \( 2 \) to \( n \).

The next line contains \( n \) integers, representing the weight \( a_i \) for each node \( i \).

The last line contains \( n \) integers, representing the weight \( b_i \) for each node \( i \).

The root node's index is \( 1 \).

Output Format

Output a single integer, the minimum value of \( W \).

Sample Input and Output

Input Sample #1

3
1 2
5 7 12
1 1 10

Output Sample #1

2

Input Sample #2

3
1 1
2 2 12
2 3 4

Output Sample #2

9

Input Sample #3

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

Output Sample #3

223

Input Sample #4

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

Output Sample #4

124

Notes/Hints

Sample Explanation

Input #1:

• Activate node 1, assimilate nodes 2 and 3, resulting in a Z cell with vitality \( h_z = 24 \), volume \( v_z = 12 \), and mutation index \( d_z = \frac{24}{12} = 2 \).
• The total minimum activation agent consumption for 1 activation is \( c_1 = t \times \lceil d_z \rceil = 1 \times \lceil \frac{24}{12} \rceil = 1 \times 2 = 2 \).

Input #2:

• Activate node 1, assimilate node 2, resulting in a Z cell with vitality \( h_z = 4 \), volume \( v_z = 5 \), and mutation index \( d_z = \frac{4}{5} \). The activation agent consumption for this activation is \( c_1 = t \times \lceil d_z \rceil = 1 \times \lceil \frac{4}{5} \rceil = 1 \times 1 = 1 \). The Z cell releases pheromones, increasing node 3's vitality by 1, making it 13.
• Activate node 3, no assimilation, resulting in a Z cell with vitality \( h_z = 13 \), volume \( v_z = 4 \), and mutation index \( d_z = \frac{13}{4} \). The activation agent 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 total minimum activation agent consumption for 2 activations is \( c_1 + c_2 = 1 + 8 = 9 \).

Input #3:

• Activate node 1, no assimilation, resulting in a Z cell with mutation index \( d_z = \frac{1}{1} = 1 \). Total activation agent consumption \( c_1 = t \times \lceil d_z \rceil = 1 \times \lceil 1 \rceil = 1 \). The Z cell releases pheromones, increasing nodes 2 and 5's vitality by 1 each, making them 8 and 10 respectively.
• Activate node 2, no assimilation, resulting in a Z cell with mutation index \( d_z = \frac{8}{1} = 8 \). Total activation agent consumption \( c_2 = t \times \lceil d_z \rceil = 2 \times \lceil 8 \rceil = 16 \). The Z cell releases pheromones, increasing nodes 3 and 4's vitality by 8 each, making them 18 and 28 respectively.
• Activate node 4, no assimilation, resulting in a Z cell with mutation index \( d_z = \frac{28}{1} = 28 \). Total activation agent consumption \( c_3 = t \times \lceil d_z \rceil = 3 \times \lceil 28 \rceil = 84 \).
• Activate node 3, no assimilation, resulting in a Z cell with mutation index \( d_z = \frac{18}{1} = 18 \). Total activation agent consumption \( c_4 = t \times \lceil d_z \rceil = 4 \times \lceil 18 \rceil = 72 \).
• Activate node 5, no assimilation, resulting in a Z cell with mutation index \( d_z = \frac{10}{1} = 10 \). Total activation agent consumption \( c_5 = t \times \lceil d_z \rceil = 5 \times \lceil 10 \rceil = 50 \).
• The total minimum activation agent consumption for 5 activations is \( c_1 + c_2 + c_3 + c_4 + c_5 = 1 + 16 + 84 + 72 + 50 = 223 \).

Input #4:

• Activate node 1, no assimilation, resulting in a Z cell with mutation index \( d_z = \frac{4}{1} \). Pheromones increase nodes 2, 5, and 9's vitality by 4 each. Activation agent consumption \( c_1 = 1 \times \lceil \frac{4}{1} \rceil = 1 \times 4 = 4 \).
• Activate node 5, assimilate nodes 6, 7, 8, resulting in a Z cell with mutation index \( d_z = \frac{84}{4} \). Activation agent consumption \( c_2 = 2 \times \lceil \frac{84}{4} \rceil = 2 \times 21 = 42 \).
• Activate node 9, assimilate nodes 10, 11, 12, resulting in a Z cell with mutation index \( d_z = \frac{71}{4} \). Activation agent consumption \( c_3 = 3 \times \lceil \frac{71}{4} \rceil = 3 \times 18 = 54 \).
• Activate node 2, assimilate nodes 3, 4, resulting in a Z cell with mutation index \( d_z = \frac{17}{3} \). Activation agent consumption \( c_4 = 4 \times \lceil \frac{17}{3} \rceil = 4 \times 6 = 24 \).
• The total minimum activation agent consumption for 4 activations is \( c_1 + c_2 + c_3 + c_4 = 4 + 42 + 54 + 24 = 124 \).

Data Range

This problem uses subtask-based scoring. Some subtasks have large input files, so use appropriate input reading methods.

• Special Property A: The given rooted tree is a star graph. \( \forall \ 2 \leq i \leq n \), \( f_i = 1 \).
• Special Property B: The given rooted tree is a directed chain. \( \forall \ 2 \leq i \leq n \), \( f_i = i - 1 \).
• Special Property C: Data is randomly generated. \( \forall \ 2 \leq i \leq n \), \( f_i \) is a randomly chosen integer from \( [1, i - 1] \). \( h_i, v_i \) are randomly chosen integers 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} \).

见题面 Input 部分

见题面 Output 部分