F - 01 on Tree

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1700

問題文

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

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

頂点を並べ終えたあと、頂点に書かれている数を頂点の並び順に沿って並べた数列を X とします。 すぬけ君は、X の転倒数 ( ※ ) を最小化したいです。 X の転倒数の最小値を求めてください。

注釈

ある長さ 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

出力

数列 X の転倒数の最小値を出力せよ。


入力例 1

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

出力例 1

4

頂点を 1, 3, 5, 6, 2, 4 の順に並べると、X = (0, 1, 0, 0, 1, 0) となり、 転倒数は 4 になります。 これ以上転倒数を小さくすることは出来ないので、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