题目描述

一个以某个节点为根的树称为等距树，当且仅当它的所有叶子到根的距离都相等。两个节点之间的距离定义为它们之间唯一简单路径上的边数。

例如，下面这棵以节点 $1$ 为根的树是等距树：

而下面这棵同样以节点 $1$ 为根的树不是等距树：

因为节点 $4,5,6$ 到根节点 $1$ 的距离并不全都相等。

树的价值

考虑一棵有 $N$ 个节点的树 $A$，节点编号为 $1,2,\ldots,N$。每个节点 $i$ 有一个权值 $w(i)$，权值可以为负数。

树 $A$ 的价值记为 $\operatorname{val}(A)$，定义如下。

我们可以不断删除当前树中的叶子，但必须保留根节点。经过若干次删除后，剩下的树需要成为等距树，或者原本就保持为等距树。某个节点可以在其他节点被删除后变成叶子，并在之后被删除。

设最终留下的节点为 $x_1,x_2,\ldots,x_k$。在所有合法删除方式中，$\operatorname{val}(A)$ 等于最终留下节点权值和的最大可能值：

$$\operatorname{val}(A)=\max \sum_{j=1}^k w(x_j).$$

例如，考虑上面第二棵有 $6$ 个节点的树。可能留下的节点集合包括：

• $\{1,2,3,5,6\}$：删除节点 $4$；
• $\{1,2,3,4\}$：删除节点 $5,6$；
• $\{1,2\}$：按顺序删除节点 $4,5,6,3$；
• $\{1\}$：按顺序删除节点 $4,5,6,3,2$。

若这棵树的权值为 $w(1),w(2),\ldots,w(6)$，则它的价值为：

$$\max\bigl( w(1)+w(2)+w(3)+w(5)+w(6),\ w(1)+w(2)+w(3)+w(4),\ w(1)+w(2),\ w(1) \bigr).$$

任务

给定一棵以节点 $1$ 为根、共有 $N$ 个节点的树 $A$，以及每个节点的权值 $w(1),w(2),\ldots,w(N)$。

记 $A_i$ 为以节点 $i$ 为根的子树。请计算：

$$\operatorname{val}(A_1),\operatorname{val}(A_2),\ldots,\operatorname{val}(A_N).$$

输入格式

第一行包含一个整数 $N$，表示树的节点数。

第二行包含 $N$ 个整数 $w(1),w(2),\ldots,w(N)$，表示各节点权值。

第三行包含 $N-1$ 个整数 $t(2),t(3),\ldots,t(N)$。它们表示树中存在如下边：

$$2-t(2),\ 3-t(3),\ \ldots,\ N-t(N).$$

输出格式

输出一行，包含 $N$ 个整数，依次为

$$\operatorname{val}(A_1),\operatorname{val}(A_2),\ldots,\operatorname{val}(A_N),$$

相邻整数之间用空格分隔。

数据范围与子任务

• $1\le N\le 1000000$；
• $-10^9\le w(i)\le 10^9$，对所有 $1\le i\le N$；
• $1\le t(i)\le N$，对所有 $2\le i\le N$。

子任务	分值	限制
1	9	$t(i)=i-1$，对所有 $2\le i\le N$
2	12	$1\le N\le 100$
3	21	$1\le N\le 5000$
4	44	$1\le N\le 100000$
5	14	无额外限制

样例

输入

6
0 -10 10 1 -1 -1
1 2 2 3 3

输出

1 1 10 1 -1 -1

样例解释

这正是题面中的第二棵树，共 $6$ 个节点。节点 $1,2,3,4,5,6$ 的权值分别为 $0,-10,10,1,-1,-1$。

对于整棵树，留下节点集合 $\{1,2,3,4\}$ 时权值和为 $1$，这是最大值。因此 $\operatorname{val}(A_1)=1$。其他节点对应的子树价值依次为 $1,10,1,-1,-1$。