[AGC023F] 01 on Tree

- 给出一棵 $n$ 个节点的树，以及一个空序列。 - 每个节点上有一个取值在 $\{0, 1\}$ 中的数。 - 每次你可以选择没有父亲节点的点删除，并且将这个节点上的数字放在当前数列末尾。 - 请你求出这个数列可能得到的最小逆序对数。 - $n \leq 2 \times 10^5$

[problemUrl]: https://atcoder.jp/contests/agc023/tasks/agc023_f すぬけ君は、$ N $ 頂点からなる根付き木を持っています。 頂点には $ 1 $ から $ N $ までの番号が振られています。 頂点 $ 1 $ はこの木の根です。 頂点 $ i $ ( $ 2\leq\ i\ \leq\ N $ ) の親は頂点 $ P_i $ ( $ P_i\ <\ i $ ) です。 各頂点には、$ 0 $ または $ 1 $ が書かれていて、頂点 $ i $ に書かれている数は $ V_i $ です。 すぬけ君は、この木の頂点を横一列に並べたいと考えています。 その際、どの頂点についても、その頂点より右側にその頂点の先祖となる頂点がないようにします。 頂点を並べ終えたあと、頂点に書かれている数を頂点の並び順に沿って並べた数列を $ X $ とします。 すぬけ君は、$ X $ の転倒数 ( ※ ) を最小化したいです。 $ X $ の転倒数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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

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

### 注釈 ある長さ $ 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 $ ) - 入力はすべて整数である。 ### Sample Explanation 1 頂点を $ 1,\ 3,\ 5,\ 6,\ 2,\ 4 $ の順に並べると、$ X\ =\ (0,\ 1,\ 0,\ 0,\ 1,\ 0) $ となり、 転倒数は $ 4 $ になります。 これ以上転倒数を小さくすることは出来ないので、$ 4 $ を出力します。 ### Sample Explanation 2 $ X\ =\ (0) $ で、転倒数は $ 0 $ です。