Sim-4-15 | Echidistant

Iaroslav-Menelaos Trapanache, known as the Thunderbolt of the Lower Danube, or (to his close friends) the Pharaoh, wants to become wiser, and feels like solving a computer science problem about trees that are as equidistant and correct as he is, so he composed the following problem.

Equidistant tree. A rooted tree $A$ is called equidistant if all its leaves are at the same distance from the root. (Recall that the distance between two nodes is given by the number of edges of the unique elementary path between the two nodes.)

For example, the following tree rooted at node $1$ is equidistant:

, whereas the following one (also rooted at node $1$) is not equidistant:

, because the distances from node $1$ to nodes $4$, $5$, $6$ are not all equal.

Value of a tree. Consider a tree $A$ with nodes numbered $1, \ldots, N$, where each node $i = 1, \ldots, N$ has a weight $w(i)$ (which can also be negative). The value of tree $A$, denoted $\text{val}(A)$, is defined as follows. Consider any way of successively removing leaves of tree $A$ such that the tree becomes or remains equidistant as a result, while keeping the root node. (We may remove a node that becomes a leaf as a result of removing other nodes.) Let $x_1, \ldots, x_k$ be the nodes remaining after this removal process. The value $\text{val}(A)$ of $A$ is the maximum possible sum $w(x_1) + \ldots + w(x_k)$ over all ways of removing leaves from $A$.

For example, let's consider the second tree above (the one with $6$ nodes). Some of the sets of nodes that can remain after removals are $\{1, 2, 3, 5, 6\}$ (we remove node $4$), $\{1, 2, 3, 4\}$ (we remove nodes $5$, $6$), $\{1, 2\}$ (we remove nodes $4$, $5$, $6$, $3$ in this order), and $\{1\}$ (we remove nodes $4$, $5$, $6$, $3$, $2$, in this order). If we assign this tree the weights $w(1), \ldots, w(6)$, then its value is: $\max(w(1) + w(2) + w(3) + w(5) + w(6),\ w(1) + w(2) + w(3) + w(4),\ w(1) + w(2),\ w(1))$.

Requirement

We are given a tree $A$ with $N$ nodes rooted at node $1$, and with weights $w(1), \ldots, w(N)$. Let $A_i$ be the subtree of $A$ rooted at node $i$. Compute $\text{val}(A_1), \ldots, \text{val}(A_N)$.

Input Data

On the first line of the input file echidistant.in is the number $N$ of nodes of tree $A$. On the second line are the numbers $w(1), \ldots, w(N)$ in order, separated by spaces. On the third line are $N - 1$ numbers $t(2), \ldots, t(N)$, representing the fact that the edges of the tree are $2 - t(2)$, $3 - t(3)$, $\ldots$, $N - t(N)$.

Output Data

The single line of the output file echidistant.out contains $N$ numbers, namely $\text{val}(A_1), \ldots, \text{val}(A_N)$ separated by spaces, in this order.

Constraints and Notes

• $1 \leq N \leq 1 \ 000 \ 000$
• $−1 \ 000 \ 000 \ 000 \leq w(i) \leq 1 \ 000 \ 000 \ 000$ for $1 \leq i \leq N$
• $1 \leq t(i) \leq N$ for $1 \leq i \leq N$

Example

echidistant.in

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

echidistant.out

1 1 10 1 -1 -1

Explanation

This is the second tree from the statement, the one with $6$ nodes, where we assign the weights $[0, -10, 10, 1, -1, -1]$ to nodes $[1, 2, 3, 4, 5, 6]$.