G. 蒙自校园

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

蒙自校园

蒙自一中的校园里散布着 $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$ 之间有一条边。

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