P8511 [Ynoi Easy Round 2021] TEST_68

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$.

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 $n$ lines, each containing one integer. The integer on the $i$-th line is the answer for node $i$.

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