#A3016. Power Strip

Power Strip

题目描述

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

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

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

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

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

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

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

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

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

输入格式

输入共三行。

第一行为一个整数 nn,代表插排数量。

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

第三行 nn 个整数 a1,a2,,ana _ 1, a _ 2, \cdots, a _ n,代表 1n1 \sim n 插排上插上的的充电器数量。

输出格式

输出一行。

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

6
1 2 1 4 5
1 2 3 1 2 4
13 5 3 7 6 4

提示

【样例 #1 解释】

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

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

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

【数据规模与约定】

对于前 10%10\% 的数据,保证 n=2n = 2

对于前 20%20\% 的数据,保证 n10n \leq 10

对于前 50%50\% 的数据,保证 n5×103n \leq 5 \times 10 ^ 3

对于另外 10%10\% 的数据,保证对任意的 2in,ui=i12 \leq i \leq n, u_i = i - 1

对于另外 10%10\% 的数据,保证对任意的 2in,ui=12 \leq i \leq n, u_i = 1

对于所有数据,保证 2n1×106,0ai109,1ui<i2 \leq n \leq 1 \times 10 ^ 6, 0 \leq a _ i \leq 10 ^ 9, 1 \leq u _ i < i