题目描述

理塘大学举行了第五人格校内排位赛，很多同学带了自己的笔记本电脑用来比赛。笔记本需要供电，但是很快同学们发现了一个问题，赛场里只有一个插座！因此同学们将自己的插排带到了赛场里。

具体的，同学们一共带来了 $n$ 个插排，我们分别将其标号为 $1 \sim n$。

下一个问题是插排的安装问题。由于赛场里只有一个插座，因此同学们只能用如图的 “插排插插排” 的方式。

$$\begin{matrix} \color{red} \small \text{请注意，这种情况只是服务于题目背景，但是十分不符合用电安全！} \\\color{red} \small \text{在生活用电中，请保证安全至上！}\end{matrix} $$

具体的，你会得到一个长度为 $n - 1$ 的序列 $u _ 2, \cdots, u _ n$。 除编号为 $1$ 的插排连接在插座上外，$u _ i$ 代表编号为 $i$ 的插排连接在 $u _ i$ 编号的插排上，我们保证 $u _ i < i$。

插排安装好后，同学们将充电器插在了不同的插座上。最后，我们可以用一个序列 $a _ 1, a _ 2, \cdots, a _ n$ 表示充电器的使用情况。具体的，对于标号为 $i$ 的插座，其被插上了 $a _ i$ 个充电器。

我们定义插排 $i$ 向某个充电器供电，当且仅当电流从赛场中的唯一一个插座流向这个充电器的时候，经过了插排 $i$。

如果对供电的概念有疑问，可以参照样例解释 #1进一步理解。

现在同学们想要知道，对于每一个插排，这个插排在向几个充电器供电。然而这个问题对于他们来说太难，所以他们找到了你，希望你能够帮他们解决这个问题。

输入格式

输入共三行。

第一行为一个整数 $n$，代表插排数量。

第二行 $n - 1$ 个整数 $u _ \bold{2}, u _ 3, \cdots, u _ n$，代表第 $2 \sim n$ 号插排连接的插排序号。

第三行 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，代表 $1 \sim n$ 插排上插上的的充电器数量。

输出格式

输出一行。

第一行为 $n$ 个整数，以一个空格隔开，代表每个插排供电的充电器数量。

样例 #1

样例输入 #1

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

样例输出 #1

13 5 3 7 6 4

提示

【样例 #1 解释】

我们使用紫色矩形表示一个充电器，样例 #1 的插排排布如下图：

以 $4$ 号插排举例，显然 $4, 5, 6$ 号插排上的充电器供电都需要经过 $4$ 号插排。电流方向如下图蓝色箭头所示。

$4$ 号插排供电的充电器共有 $1 + 2 + 4 = 7$ 个。

【数据规模与约定】

对于前 $10\%$ 的数据，保证 $n = 2$。

对于前 $20\%$ 的数据，保证 $n \leq 10$。

对于前 $50\%$ 的数据，保证 $n \leq 5 \times 10 ^ 3$。

对于另外 $10\%$ 的数据，保证对任意的 $2 \leq i \leq n, u_i = i - 1$。

对于另外 $10\%$ 的数据，保证对任意的 $2 \leq i \leq n, u_i = 1$。

对于所有数据，保证 $2 \leq n \leq 1 \times 10 ^ 6, 0 \leq a _ i \leq 10 ^ 9, 1 \leq u _ i < i$。