Gaeul is obsessed with kitsch items, and after lots of thrifting she's preparing to assemble them onto a hanging mobile. She already has a design in mind, but is struggling to put items onto it, and needs your help!
Gaeul's current design can be modeled as a tree with $$$n$$$ nodes rooted at node $$$1$$$. These nodes are either leaf nodes (which will contain an ornament) or internal nodes (which have negligible weight and don't hold ornaments). Currently, node $$$i$$$ has weight $$$w_i$$$, which is zero if it is an internal node. A node's balance factor is the total weight of all nodes in its subtree, and a node is "balanced" if all of its children have the same balance factor (all leaves are trivially balanced). Naturally, Gaeul's goal is to ensure that all nodes are balanced.
Gaeul's tree might be unbalanced right now, but she is able to add or remove material from individual ornaments. Formally, she has the ability to take any ornament and change its weight to any positive real number. Gaeul is in a rush, however, and can't afford to change too many ornaments, so she needs your help to find the minimum number she needs to change.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the number of nodes.
The second line contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$), where $$$p_i$$$ is the parent of node $$$i$$$. If $$$n=1$$$, this line is empty.
The third line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$, the weights of the nodes. If $$$i$$$ is an internal node then $$$w_i = 0$$$, otherwise it lies in the range $$$1 \le w_i \le 10^9$$$.
Output a single integer: the minimum number of ornaments that need to be changed.
61 1 2 4 40 0 1 0 1 1
1
61 1 1 2 20 0 1 1 1 5
2
15
0
The first sample test case is drawn below, where the red numbers represent ornament weights and the green numbers represent balance factors. By changing the ornament at node $$$3$$$ to weight $$$2$$$, the entire tree will be balanced.
In the second test case, one optimal solution involves changing nodes $$$5$$$ and $$$6$$$.
The third test case is a single ornament and thus trivially balanced.
| Name |
|---|


