配点 : $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$ の転倒数の最小値を出力せよ。

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

4

頂点を $1, 3, 5, 6, 2, 4$ の順に並べると、$X = (0, 1, 0, 0, 1, 0)$ となり、 転倒数は $4$ になります。 これ以上転倒数を小さくすることは出来ないので、$4$ を出力します。

1

0

0

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

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

31