Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Applying XOR twice cancels it, and each edge operation toggles two nodes. Therefore the set of nodes ultimately toggled must have even size. Conversely, any pair of nodes can be toggled by operating along their connecting path: internal nodes are toggled twice. Pairing up any even-sized selection makes it achievable.

Approach

Start with the sum of the original values. Compute each node's gain, (value XOR k) - value, and sort all gains in descending order. Consider adjacent pairs in this sorted list and add a pair's gain when its sum is positive.

For any fixed even number of selected nodes, the largest gains give the best sum. Sorted adjacent-pair sums are nonincreasing, so taking the positive pairs chooses the best even-sized prefix. A negative individual gain may still be worthwhile when paired with a larger positive gain. The tree edges need not be inspected because connectivity already guarantees the required pair operations are possible.

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        n = len(nums)
        diff = [0] * n
        for i in range(n):
            diff[i] = (nums[i] ^ k) - nums[i]
        diff.sort(reverse = True)

        total = sum(nums)
        for i in range(1, n, 2):
            pair = diff[i] + diff[i - 1]
            if pair > 0:
                total += pair

        return total

Complexity analysis

Let n = nums.length. Time: O(n log n). Auxiliary space: O(n) for the sorted gain array.