You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在中国传统的阴阳学说中，阴阳代表着事物的两种对立又统一的状态，二者共存方为平衡。小明受此启发，将树结构中的节点赋予 “阴”（白色）与 “阳”（黑色）两种状态，构建了一个动态变化的 “阴阳树” 模型。初始时，所有节点均为 “阴”（白色），随着节点按顺序被染成 “阳”（黑色），树中以各节点为根的子树会因阴阳状态的变化而呈现不同的特性。其中，阴阳子树定义为子树内同时存在阴阳两种状态的节点，象征着阴阳调和的局部结构。小明希望通过分析每次染色后阴阳子树的数量变化，探索树结构中阴阳状态的动态平衡规律。

题目描述

小明构建了一棵以 $1$ 号节点为根的有根树，初始时所有节点均为白色（阴）。给定一个长度为 $n$ 的排列 $p$，表示节点的染色顺序：第 $i$ 次操作将节点 $p_i$ 染成黑色（阳），且颜色一旦改变便不再恢复。定义阴阳子树为：以某个节点为根的子树（包含该节点及其所有后代）中，同时存在黑色（阳）和白色（阴）节点。每次染色操作后，需要输出当前树中阴阳子树的个数，以反映树结构中阴阳共存的局部区域数量变化。

输入格式

输入数据第一行包含一个正整数 $n$，为树的节点数。

输入数据的第二行包含 $n−1$ 个正整数$a_i(1 \le a_i \le i−1)$ ，其中第 $i$ 个整数 $a_i$ 代表节点 $i+1$ 的父亲.

输入数据的第三行包含 $n$ 个由空格隔开的正整数，为节点染色的顺序。

输出格式

共包含 $n$ 个整数，第 $i$ 个整数为第 $i$ 次染色后阴阳子树的个数。每个整数间以一个空格分隔

样例

输入

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

输出

2 1 2 2 2 0

样例解释

对于第一个样例： 初始状态

第一次染色

$1 \ 2$ 号节点符合要求

第二次染色

$1$ 号节点符合要求

第三次染色

$1 \ 3$ 号节点符合要求

第四次染色

$1 \ 3$ 号节点符合要求

第五次染色

$3$ 号节点符合要求

第六次染色

无结点符合要求

限制与约定

对于 $40\%$的样例 保证 $1\le n \le 100$

对于 $100\%$的样例 保证 $1\le n \le 10^5$ $1 \le p_i \le n$ , 并且保证给出的 $p$ 是一个排列

• 时间限制: $2 s$
• 空间限制: $256 MB$