Power Strip

来源：洛谷 B3681（[语言月赛202211] Power Strip）

题目描述

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

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

下一个问题是插排的安装问题。由于赛场里只有一个插座，因此同学们只能用“插排插插排”的方式：编号为 $1$ 的插排连接在插座上，其它插排依次插在前面的插排上。

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

每个插排上还插了若干充电器。请计算每个插排供电的充电器数量：一个插排供电的充电器，包括插在它自己上面的充电器，以及插在所有“直接或间接插在它上面”的插排上的充电器。

输入格式

输入共三行。

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

第二行 $n-1$ 个整数 $u_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 解释

以 $4$ 号插排举例，显然 $4, 5, 6$ 号插排上的充电器供电都需要经过 $4$ 号插排。$4$ 号插排供电的充电器共有 $1 + 2 + 4 = 7$ 个。

数据规模与约定

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

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

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

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

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

对于所有数据，保证 $2 \le n \le 10^6$，$0 \le a_i \le 10^9$，$1 \le u_i < i$。