D. Strong Tree
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
If you seek a tree, there was no bluff!

Up for it, or are you not strong enough?

There is a rooted tree, consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$. Each vertex $$$i$$$ has a value $$$a_i$$$ and a unique rank $$$r_i$$$.

The strength of a simple path from vertex $$$u$$$ to vertex $$$v$$$ is the sum of values of each of the vertices on the unique simple path from $$$u$$$ to $$$v$$$.

For each vertex $$$i$$$ from $$$1$$$ to $$$n$$$, find the maximum strength of any simple path from $$$u$$$ to $$$v$$$ that satisfies the following conditions:

  • Vertex $$$i$$$ is an ancestor of both $$$u$$$ and $$$v$$$.
  • The simple path from $$$u$$$ to $$$v$$$ goes through vertex $$$i$$$.
  • $$$r_j \leq r_i$$$ for any vertex $$$j$$$ on the simple path from $$$u$$$ to $$$v$$$.
Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$; $$$p_i \neq i$$$), where $$$p_i$$$ is the parent of vertex $$$i$$$.

The third line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^7 \leq a_i \leq 10^7$$$), where $$$a_i$$$ is the value of vertex $$$i$$$.

The fourth line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \leq r_i \leq n$$$), where $$$r_i$$$ is the rank of vertex $$$i$$$. It is guaranteed that $$$r_i \neq r_j$$$ for all $$$i \neq j$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$

Output

For each test case print $$$n$$$ integers on a single line — the $$$i$$$-th integer represents the answer for vertex $$$i$$$.

Example
Input
2
4
1 1 2
6 5 9 7
3 1 2 4
6
1 1 3 3 3
5 2 -9 4 -16 36
6 1 4 2 3 5
Output
20 5 9 7 
34 2 -5 4 -16 36
Note
Figure: Tree from the 1st test case in sample

Each vertex $$$i$$$ is labeled above it as $$$a_i(r_i)$$$ in the figure.

In the 1st test case, for vertex $$$1$$$, the optimal path is from vertex $$$2$$$ to vertex $$$3$$$, since the path satisfies all the required conditions. We cannot include vertex $$$4$$$ in the path since it has a higher rank than vertex $$$1$$$.

For the remaining vertices, the optimal path includes only the vertex itself.