Maximum XOR Outside Subtree

You are given a tree with \(n\) nodes. For each node \(i\), a weight \(a_i\) is given. The tree is rooted at node 1. For every node \(x\), let its subtree be defined as \(x\) and all its descendants. The answer for node \(x\) is defined as the maximum value of \(a_i \oplus a_j\) over all pairs of nodes \(i,j\) that lie outside of the subtree of \(x\). Note that the two nodes chosen can be the same (in which case \(a_i \oplus a_i = 0\)). If there are no two nodes outside the subtree of \(x\) (i.e. when the set is empty or has a single element), then the answer for \(x\) is considered to be 0.

Input Format: The input begins with an integer \(n\) representing the number of nodes. The next line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) is the weight of node \(i\). Following that, there are \(n-1\) lines each containing two integers \(u\) and \(v\) indicating an edge between nodes \(u\) and \(v\>.

Output Format: For each node from 1 to \(n\), output its answer on a new line.

inputFormat

The first line contains an integer \(n\) (the number of nodes). The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the weight of each node. The following \(n - 1\) lines each contains two space-separated integers \(u\) and \(v\) indicating an undirected edge in the tree.

outputFormat

Output \(n\) lines, where the \(i\)-th line contains the maximum \(a_i \oplus a_j\) for nodes \(i,j\) chosen from outside the subtree of node \(i\). If no valid pair exists, output 0 for that node.

sample

3
1 2 3
1 2
2 3

0
0
3