Edge Toggles on a Tree

Hard

You are given a tree with n nodes numbered 0 to n - 1; edges[i] = [u, v] is an edge between u and v. Node i holds the number values[i], and you also get a key. You may repeat the following any number of times, including zero: pick any edge [u, v] and replace both numbers at its ends, values[u] = values[u] XOR key and values[v] = values[v] XOR key. Return the largest total of all node values you can reach.

Example 1

values=[4, 1, 6], key=5, edges=[[0, 1], [1, 2]] → 11

Toggling turns 4 → 1, 1 → 4, 6 → 3. Only the middle one pays off, yet nodes always change in pairs. Toggling edge (0, 1) gives [1, 4, 6], the same sum 11 as doing nothing; nothing beats it.

Example 2

values=[10, 10], key=1, edges=[[0, 1]] → 22

One toggle gives [11, 11], sum 22.

Example 3

values=[1, 2, 3, 0], key=6, edges=[[0, 1], [0, 2], [0, 3]] → 22

Constraints

2 ≤ n = len(values) ≤ 2 · 10⁴
1 ≤ key ≤ 10⁹
0 ≤ values[i] ≤ 10⁹
len(edges) = n - 1 and the edges form a tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation Tree Array Dynamic Programming Sorting

Similar problems

Strongest Product Team Medium Biggest Number Divisible by Three Hard Best Order for a Tasting Menu Hard Harvesting a Tree: Toll or Half Hard Fewest Meetings to Cancel Medium

Input

values=[4, 1, 6], key=5, edges=[[0, 1], [1, 2]]

Expected

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