Contest Duration: - (local time) (140 minutes) Back to Home
F - 01 on Tree /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

すぬけ君は、N 頂点からなる根付き木を持っています。 頂点には 1 から N までの番号が振られています。 頂点 1 はこの木の根です。 頂点 i ( 2\leq i \leq N ) の親は頂点 P_i ( P_i < i ) です。 各頂点には、0 または 1 が書かれていて、頂点 i に書かれている数は V_i です。

すぬけ君は、この木の頂点を横一列に並べたいと考えています。 その際、どの頂点についても、その頂点より右側にその頂点の先祖となる頂点がないようにします。

注釈

ある長さ N の数列 Z の転倒数とは、整数 i, j ( 1 \leq i < j \leq N ) の組であって、Z_i > Z_j を満たすものの個数を意味します。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i < i ( 2 \leq i \leq N )
• 0 \leq V_i \leq 1 ( 1 \leq i \leq N )
• 入力はすべて整数である。

入力

N
P_2 P_3 ... P_N
V_1 V_2 ... V_N


入力例 1

6
1 1 2 3 3
0 1 1 0 0 0


出力例 1

4


入力例 2

1

0


出力例 2

0


X = (0) で、転倒数は 0 です。

入力例 3

15
1 2 3 2 5 6 2 2 9 10 1 12 13 12
1 1 1 0 1 1 0 0 1 0 0 1 1 0 0


出力例 3

31


Score : 1700 points

Problem Statement

Snuke has a rooted tree with N vertices, numbered 1 through N. Vertex 1 is the root of the tree, and the parent of Vertex i ( 2\leq i \leq N ) is Vertex P_i ( P_i < i ). There is a number, 0 or 1, written on each vertex. The number written on Vertex i is V_i.

Snuke would like to arrange the vertices of this tree in a horizontal row. Here, for every vertex, there should be no ancestor of that vertex to the right of that vertex.

After arranging the vertices, let X be the sequence obtained by reading the numbers written on the vertices from left to right in the arrangement. Snuke would like to minimize the inversion number of X. Find the minimum possible inversion number of X.

Notes

The inversion number of a sequence Z whose length N is the number of pairs of integers i and j ( 1 \leq i < j \leq N ) such that Z_i > Z_j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i < i ( 2 \leq i \leq N )
• 0 \leq V_i \leq 1 ( 1 \leq i \leq N )
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_2 P_3 ... P_N
V_1 V_2 ... V_N


Output

Print the minimum possible inversion number of X.

Sample Input 1

6
1 1 2 3 3
0 1 1 0 0 0


Sample Output 1

4


When the vertices are arranged in the order 1, 3, 5, 6, 2, 4, X will be (0, 1, 0, 0, 1, 0), whose inversion number is 4. It is impossible to have fewer inversions, so the answer is 4.

Sample Input 2

1

0


Sample Output 2

0


X = (0), whose inversion number is 0.

Sample Input 3

15
1 2 3 2 5 6 2 2 9 10 1 12 13 12
1 1 1 0 1 1 0 0 1 0 0 1 1 0 0


Sample Output 3

31