题目描述

在本题中，我们定义红黑树为既包含黑点又包含红点的树。

给定一棵 $n$ 个点的有根树，根为节点 $1$，初始每个点都是红色，有 $n$ 次操作，每次操作会把 $p_i$ 变成黑色，保证操作序列 $p$ 是一个排列，即每次操作的点都不相同。

每次操作完成后，你需要输出有多少个子树是红黑子树，即子树内既包含黑点又包含红点。

• 即有多少个点 $i$，以 $i$ 为根的这棵子树是一棵红黑树。

输入格式

从 tree.in 文件读入数据。

第一行一个整数 $n$。

第二行 $n-1$ 个整数，第 $i$ 个整数表示第 $i+1$ 个点的父亲节点 $fa_{i}$。

第三行 $n$ 个整数 $p_i$ ，表示操作序列。

输出格式

输出到 tree.out 文件。

一行 $n$ 个整数，表示每次操作后有多少个子树是红黑子树。

输入输出样例

6
1 1 2 3 3
2 4 6 1 3 5

2 1 2 2 2 0

样例2

点击链接 ex_tree2.in 和 ex_tree2.out 文件下载大样例 2 的输入数据和输出数据。

说明/提示

对于 $20\%$ 的数据，$fa_i=i-1$

对于 $50\%$ 的数据，$n\leq 5000$

对于 $100\%$ 的数据，$1\leq n \leq 10^5,fa_i<i$