小柒的特殊双节点

题号：NC295053
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小柒被啦啦啦送了一棵树，这颗树有 $n$ 个节点，每个节点 $i$ 有一个权值 $a_i$ 。
$\hspace{15pt}$ 但是这颗树不是白送的，啦啦啦向小柒提出了一个问题。假设以 $1$ 号节点为根节点，对于每一个节点 $i$ ，找到另一个节点 $j$ ，使得：
$\hspace{23pt}\bullet\,$ $i$ 既不是 $j$ 的祖先节点也不是 $j$ 的子孙节点（善意的提示 $i$ 可以等于 $j$ ）；
$\hspace{23pt}\bullet\,$ $a_i \oplus a_j$ 最大。
$\hspace{15pt}$ 小柒最近正忙于考研，没有思考这个问题，所以请你来帮忙，按照节点编号顺序，从小到大输出每一个节点的最大异或值。

【名词解释】
$\hspace{15pt}$ $\oplus$ ：代表位运算中的异或运算。

输入描述:

第一行输入一个整数  代表这颗树节点的数量。 
第二行输入  个整数  代表每个结点的权值。 
此后  行，第  行输入两个整数  代表第  条树边连接  号节点与  号节点。保证输入的树是一棵合法的树。

输出描述:

在一行上输出  个整数，第  个整数表示节点  可以找到的节点  的最大异或值。

示例1

输入

复制

7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7

输出

复制

0 5 7 7 6 4 5

备注:

如果您使用 C/C++，建议切换为 C++ (g++ 13) 提交，已知本题使用 C++ (clang++18) 会导致编译内存错误（Compiler exceeded MEMORY limit）。