Longest XOR Path in a Weighted Tree

You are given a weighted tree with n nodes numbered from 1 to n. Each edge has an associated weight. Your task is to find two nodes such that the XOR of the edge weights along the unique path between them is maximized.

The XOR path between two nodes is defined as the bitwise XOR (\(\oplus\)) of all the weights on the unique simple path connecting these two nodes.

Note: The tree is undirected and connected, and it contains exactly n - 1 edges.

The problem can be reduced to computing for each node the XOR from a fixed root (for instance, node 1) to that node. Then the answer is the maximum value of \(x \oplus y\) for any two such XOR prefix values. This can be efficiently done using a binary trie.

inputFormat

The first line contains a single integer n (the number of nodes in the tree).

The following n - 1 lines each contain three integers u, v and w representing an edge between nodes u and v with weight w.

It is guaranteed that the given graph is a tree.

outputFormat

Output a single integer --- the maximum XOR value of the edge weights along a path between any two nodes in the tree.

sample

3
1 2 1
2 3 2

3