All problems

Strongest Cable Path

Hard · trie

A campus network has n junction boxes, numbered from 0 to n - 1, joined by n - 1 cables so that exactly one route of cables links any two boxes. edges[i] = [u, v, key] is a cable between boxes u and v carrying a whole-number key.

A signal that travels along a route is scrambled by every cable on it: the value of the route is the bitwise XOR (^) of the keys of all its cables. XOR gives a 1 in every bit position where an odd number of the keys have a 1, so a key used twice cancels out. For example, 5 ^ 3 = 6.

Consider every route between two different boxes. Return the largest route value. If n is 1, there is no route, so return 0.

Examples

Example 1

Input: n = 4, edges = [[0, 1, 3], [1, 2, 5], [1, 3, 6]]

Output: 6

The single cables give 3, 5 and 6. The longer routes give 3 ^ 5 = 6, 3 ^ 6 = 5 and 5 ^ 6 = 3. The best is 6.

Example 2

Input: n = 3, edges = [[0, 1, 2], [1, 2, 2]]

Output: 2

The route from 0 to 2 uses the key 2 twice, so it cancels to 0. A single cable gives 2.

Example 3

Input: n = 1, edges = []

Output: 0

There is only one box, so there is no route.

Constraints