小圆前辈的异或树

题号：NC221198
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小圆前辈丢给你一颗n个节点的树，第i个点的权值为a[i]。

没啥理由，就是想让你求 $\max_{i \le j \le n } dist(i, j)$ 。

定义：dist(u, v)为u到v最短路径所经过的点的权值异或和。

第一行一个整数n。

接下来的一行有n个整数：a[1]~a[n]。

接下来有n - 1行，每行两个整数u,  v表示u和v有一条无向边（输入保证合法）。

输出一个整数为所有dist(u, v)中的最大值。

示例1

复制

6
4 4 2 2 16 8
1 2
1 3
2 4
2 5
5 6

复制

最大的为dist(4, 6) = 30。