分数: 1700 点
问题陈述
Snuke有一棵有根树 N 顶点,编号 1 通过 N。 顶点 1 是树的根,也是 Vertex 的父级 i ( 2\leq i \leq N ) 是顶点 P_i ( P_i < i )。 有一个数字, 0 or 1,写在每个顶点上。顶点上写的数字 i is V_i.
Snuke 希望将这棵树的顶点排列在水平行中。 在这里,对于每个顶点,该顶点的右侧不应有该顶点的祖先。
排列顶点后,让 X 是通过从左到右读取排列中写在顶点上的数字获得的序列。 Snuke 希望最小化反转次数 X。 求最小可能的反转数 X.
注释
的 反转数 序列的 一个序列的 Z 其长度 N 是整数对的数量 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