Three-Way Tree Cut

Hard

You are given a tree with n nodes numbered 0 to n - 1; its edges come as a list edges, where edges[i] = [a, b] joins nodes a and b. Node i holds the number values[i]. Delete exactly two different edges, which splits the tree into three connected parts. For each part, take the bitwise XOR of the numbers in all its nodes. The *spread* of the cut is the largest of the three XORs minus the smallest. Return the smallest spread you can achieve.

Example 1

values=[6, 2, 3, 7, 4], edges=[[0, 1], [1, 2], [0, 3], [3, 4]] → 1

Cutting 1–2 and 3–4 leaves {2} with XOR 3, {4} with XOR 4 and {0, 1, 3} with XOR 6 ^ 2 ^ 7 = 3. The spread is 4 − 3 = 1, and no pair of cuts does better.

Example 2

values=[9, 9, 5, 5], edges=[[0, 1], [1, 2], [2, 3]] → 5

Cutting 1–2 and 2–3 gives {0, 1} with XOR 0 and {2}, {3} with XOR 5 each, a spread of 5. No other pair of cuts does better.

Example 3

values=[1, 2, 3], edges=[[0, 1], [0, 2]] → 2

Constraints

3 ≤ n = len(values) ≤ 1000
1 ≤ values[i] ≤ 10⁸
len(edges) = n − 1, edges[i] = [a, b], 0 ≤ a, b < n, a ≠ b
The edges form a tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Tree Depth-First Search Array

Similar problems

Harvesting a Tree: Toll or Half Hard Nearest Coprime Ancestor Hard Best XOR Up the Chain of Command Hard Tree Path Without Twin Neighbours Hard Meeting Point on a Route Hard

Input

values=[6, 2, 3, 7, 4], edges=[[0, 1], [1, 2], [0, 3], [3, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 57 tests on the server, hidden ones included.