← 返回题目列表

AtCoder · agc023_f

F. 01 在树上

中文机器翻译题面 查看原题

分数: 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