蒙自校园

题目背景

蒙自一中的校园里散布着 $n$ 个景点，由 $n-1$ 条小路连接，任意两个景点之间可以互相到达。每个景点 $i$ 有一个独特的「校园魅力值」$a_i$。参赛选手们想找到一条游览路线，使得路线上所有景点的魅力值异或之和最大。

题目描述

给定一棵 $n$ 个节点的树，节点 $i$ 有权值 $a_i$。定义一条简单路径（即路径上每个节点至多经过一次）的得分为路径上所有节点权值的异或和。

求所有简单路径中的最大得分。

输入格式

第一行一个整数 $n$（$1 \le n \le 10^5$）。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 2^{20}$）。

接下来 $n-1$ 行，每行两个整数 $u, v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

输出一个整数，表示最大异或路径得分。

样例

4
1 2 3 4
1 2
2 3
2 4

7