Yet Another XOR Problem

farhanhasin Criterion 2020 Round 3
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).


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.


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


4 7 15
1 2
3 1

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


Login to submit.


71% Solution Ratio
nahid08Earliest, Feb '20
EgorKulikovFastest, 0.4s
Deshi_TouristLightest, 71 MB
Deshi_TouristShortest, 1029B
Toph uses cookies. By continuing you agree to our Cookie Policy.