题目描述

すぬけ君有一棵包含 $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$ $\cdots$ $P_N$ $V_1$ $V_2$ $\cdots$ $V_N$

输出格式

请输出数列 $X$ 的最小逆序对数。

样例 1

输入

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

输出

4

样例 2

输入

1

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

输出

31

说明/提示

注释

对于长度为 $N$ 的数列 $Z$，其逆序对数定义为满足 $1 \leq i < j \leq N$ 且 $Z_i > Z_j$ 的整数对 $(i, 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$）
• 所有输入均为整数。

样例解释 1

如果将节点按 $1,\ 3,\ 5,\ 6,\ 2,\ 4$ 的顺序排列，则 $X = (0, 1, 0, 0, 1, 0)$，其逆序对数为 $4$。无法再使逆序对数更小，因此输出 $4$。

样例解释 2

$X = (0)$，逆序对数为 $0$。

由 ChatGPT 4.1 翻译