#1566. [语言月赛202211] Power Strip

[语言月赛202211] Power Strip

题目描述

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

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

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

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

具体的,你会得到一个长度为 n−1n - 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,代表插排数量。

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

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

输出格式

输出一行。

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

样例

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

题目来源:洛谷 B3681