Problem Description

Given a tree with $n$ nodes, node $i$ has a weight $a_i$.

For each node $x$, its answer is defined as follows: among all nodes outside the subtree of $x$, choose two nodes $i, j$ (they may be the same node), and maximize $a_i$ xor $a_j$. If it is impossible to choose two nodes, then the answer for $x$ is $0$.

Input Format

The first line contains an integer $n$.

The next line contains $n-1$ integers. The $i$-th integer denotes the parent node $j$ of node $i+1$, and it is guaranteed that $j < i+1$.

The next line contains $n$ integers. The $i$-th integer denotes the weight $a_i$ of node $i$.

Output Format

Output $n$ lines, each containing one integer. The integer on the $i$-th line is the answer for node $i$.

10
1 1 2 3 2 3 6 7 7
10 6 4 10 8 10 5 3 5 4

0
15
12
15
15
15
14
15
15
15

Hint

Idea: nzhtl1477, Solution: zx2003, Code: nzhtl1477, Data: nzhtl1477.

For $10\%$ of the testdata, $1 \le n \le 10^2$.

For another $20\%$ of the testdata, $1 \le n \le 10^4$.

For another $30\%$ of the testdata, the tree is a chain.

For another $20\%$ of the testdata, $0 \le a_i \le 10^2$.

For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$ and $0 \le a_i \le 10^{18}$.

Translated by ChatGPT 5