Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Yet Another XOR Problem

By farhanhasin · Limits 3s, 1.0 GB

Given a rooted tree with N nodes where each node has a value, find a pair of nodes (u, v) so that u is an ancestor of v and the bit-wise XOR of the values of u and v is the maximum among all such pairs. The tree is always rooted at node 1.

A tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. An ancestor of a node is any node in the path from that node to the root node (including the root node itself).

Input

The first line will contain a single integer N (2 ≤ N ≤ 5×105), the number of nodes in the tree.

The second line will contain N integers, the values of the nodes. Values will be between 0 and 109 inclusive.

The following N-1 lines will contain edges ui and vi (1 ≤ ui, vi ≤ N). Input is guaranteed to form a valid tree.

Output

Print the required maximum bit-wise XOR in a single line.

Samples

InputOutput
3
4 7 15
1 2
3 1

11
InputOutput
5
11 3 7 6 14
1 2
2 3
3 4
2 5
13

Discussion

Statistics


67% Solution Ratio

nahid08Earliest, Feb '20

EgorKulikovFastest, 0.4s

Deshi_TouristLightest, 71 MB

Deshi_TouristShortest, 1029B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.