题目描述

生长壮大吧，髑髅树！

髑髅树上长出了果实，将会源源不断地生成骷髅士兵，这种生成士兵是毫无限制的，其主人小码哥对其十分自豪，称其为“神一般的能力”。

小码妹要消灭髑髅树。

髑髅树是一棵以$1$号节点为根节点的树，每个节点可以看作是髑髅树上的一个果实，有血量$hp_i$。

小码妹需要消灭所有的果实才能消灭髑髅树。一个果实只有在它的父节点被消灭之后才能被消灭，当然，根节点不需要满足这个条件就可以被消灭。消灭节点$i$的果实所需要耗费的灵力为这个果实本身的血量$hp_i$，再加上其子节点中还没有被消灭的果实的血量之和。

当然，如果没有特殊手段的话，消灭一个果实时，其子节点不会存在已经被消灭的果实。然而，小码妹的鬼道也十分厉害，她将会使用她擅长的双莲苍火坠消灭任意一个还未被消灭的果实，你可以认为使用鬼道是不消耗灵力的。

现在，小码妹想知道，如果知道自己可以使用鬼道的次数，消灭整棵髑髅树需要消耗的最小灵力是多少？

输入格式

第一行输入一个整数$n$，表示树的节点个数。 第二行输入$n$个整数$p_i(p_i<i)$，表示节点$i$的父节点编号。保证只有$p_1=0$，表示根节点为$1$。 第三行输入$n$个整数$hp_i$。

输出格式

输出一行$n+1$个整数$a_0,a_1,a_2,…,a_n$，其中$a_i$表示小码妹可以使用$i$次双莲苍火坠的情况下，消灭髑髅树的最小灵力消耗。

样例输入 #1

5
0 1 2 3 4
1 2 3 4 5

样例输出 #1

29 16 9 4 1 0

说明/提示

有$1\leq n\leq 2\times 10^3,1\leq hp_i\leq 10^9$。