P16610 [Algo Beat 008 & WWOI R3] Galactic War Zone

::::info[银河战区] 银河战区 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 太精彩了！起点和终点无法决定，游戏半途结束。终末的光芒投向大地，学校里的学生开始去食堂买汉堡。 我的起点，是学校的汉堡太好吃了。这决定了很多，比如我每天去吃一个。银河系是由几百亿个星星组成的。每天只有到十点才能去买汉堡，不然我就只能食用我的直尺了，这是宇宙中多么一个莫大的不幸。■■■■■■■■■■■■■■■■■■■■■但是想写什么，为什么什么都写不下来啊。 无论怎么选都会选中错误的，怎么挣扎都改变不了些什么呢，怎么搞都必定会失败吧，终末之时已至。不如去多吃几个汉堡。 享受当下，我能吃几个，我就吃几个。还有几天就再也买不到学校的汉堡了，学校食堂马上就没有汉堡了，这点也是假的吧，同我那可笑的荒诞的错觉一样，都是不规则的吧。 三角形的太阳在天上放着剧毒的光，这是真的吗，从来我一点都不累的，竟然有些疲惫了，太阳要掉下去了，必定会失败吧，终末之时已至，吃汉堡吧。 学校的柜子里还剩下最后几个汉堡，都是我的了！每一个都要尽情享用，在太阳落山之前，终末之时已至，不如多吃几个汉堡吧。 我感受着汉堡里的调料在我舌尖跳舞，我不禁想着，在这广大的银河中，一定也有人在跳舞吧。在被落下的太阳烧死前，金光填满了我的世界，无所谓了，无所谓了，来生还会有汉堡的。下定决心的起点，错觉与虚幻交织的终点，还会再一次出现的吧。学校食堂的汉堡，马上就会补货，我把我的胃发射到天上，残缺的身体第一次张开了对太阳的怀抱。 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

How wonderful! The starting point and the destination cannot be decided, and the game ends halfway. The light of the end shines upon the earth, and students in the school begin to go to the cafeteria to buy hamburgers. You have $n$ hamburgers, where each hamburger $i$ has a deliciousness value $a_i$. You can place these hamburgers arbitrarily on the $n$ nodes of a tree, such that each node contains exactly one hamburger. The hamburgers at school are so delicious, so we define the **total deliciousness** as follows: for every chain on the tree leading to the root node $1$, calculate the XOR sum of the deliciousness values of the hamburgers on that chain. The total deliciousness is the bitwise AND sum of all these XOR results. What is the maximum total deliciousness you can obtain after placing the hamburgers on the tree in an optimal way? I suddenly... really want... to eat... a hamburger... **Original Formal Problem Statement:** There is a tree with $n$ nodes, numbered from $1$ to $n$, with the root node being $1$; and a sequence $a$ of length $n$. You can arbitrarily rearrange the sequence $a$, and then sequentially assign the node weight of node $i$ on the tree to be $a_i$, in order to maximize the value of this tree. We define $f(i)$ as the XOR sum of the node weights (including the node itself) on the simple path from node $i$ to the root of the tree. Then, the value of the tree is defined as: $\operatorname{AND}_{i=1}^{n}f(i)$. That is, the bitwise AND sum of $f(i)$ for nodes $1$ to $n$.

The first line contains a positive integer $n$. The next line contains $n$ positive integers representing the sequence $a$. The following $n-1$ lines each contain two integers $u$ and $v$, indicating that there is an edge between node $u$ and node $v$. It is guaranteed that the graph is a tree.

Output a single non-negative integer on one line, representing the maximum value of the tree.

**This problem uses bundled testing.** For all test data, the following conditions apply: * $1 \leq u,v \leq n \leq 10^5$. * $1 \leq a_i \leq 10^9$. | Subtask Number | $n\leq$ | Special Properties | Score | | :---: | :---: | :---: | :---: | | $1$ | $9$ | None | $20$ | | $2$ | $15$ | ^ | $20$ | | $3$ | $10^3$ | ^ | $30$ | | $4$ | $10^5$ | Data is randomly generated, and $n\geq 10^4$ | $1$ | | $5$ | $10^5$ | None | $29$ | Translated by Qwen 3.6