/ 
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