Find the Maximum Sum of Node Values

hard tree greedy dp bit manipulation

Problem

You have a tree with n nodes, an array nums, and an integer k. Any number of times you may pick an edge (u,v) and replace nums[u] with nums[u] XOR k and nums[v] with nums[v] XOR k. Return the maximum possible sum of all node values.

Inputnums = [1,2,1], k = 3, edges = [[0,1],[1,2]]

Output6

XOR-ing nodes 0 and 2 gives [2,2,2] for a sum of 6; flipping an even number of nodes (here, 2) is always achievable, so 6 is the maximum.

nums array

edges as [u,v] list

def maximum_value_sum(nums, k, edges):
    total = 0
    count = 0
    min_delta = float('inf')
    for x in nums:
        xored = x ^ k
        if xored > x:
            total += xored
            count += 1
        else:
            total += x
        min_delta = min(min_delta, abs(xored - x))
    if count % 2 == 1:
        total -= min_delta
    return total

function maximumValueSum(nums, k, edges) {
  let total = 0, count = 0, minDelta = Infinity;
  for (const x of nums) {
    const xored = x ^ k;
    if (xored > x) {
      total += xored;
      count++;
    } else {
      total += x;
    }
    minDelta = Math.min(minDelta, Math.abs(xored - x));
  }
  if (count % 2 === 1) total -= minDelta;
  return total;
}

class Solution {
    public long maximumValueSum(int[] nums, int k, int[][] edges) {
        long total = 0;
        int count = 0, minDelta = Integer.MAX_VALUE;
        for (int x : nums) {
            int xored = x ^ k;
            if (xored > x) {
                total += xored;
                count++;
            } else {
                total += x;
            }
            minDelta = Math.min(minDelta, Math.abs(xored - x));
        }
        if (count % 2 == 1) total -= minDelta;
        return total;
    }
}

class Solution {
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        long long total = 0;
        int count = 0, minDelta = INT_MAX;
        for (int x : nums) {
            int xored = x ^ k;
            if (xored > x) {
                total += xored;
                count++;
            } else {
                total += x;
            }
            minDelta = min(minDelta, abs(xored - x));
        }
        if (count % 2 == 1) total -= minDelta;
        return total;
    }
};

Explanation

The key insight is about parity, not tree shape. Each operation flips two endpoints, so the total number of XOR-flipped nodes always changes by 0 or 2 — it stays even. And because the tree is connected, any even-sized set of nodes can be flipped by chaining edge operations along paths. So the only real constraint is: flip an even number of nodes.

So we decide independently, for each node, whether nums[i] XOR k beats nums[i]. We greedily take the XOR whenever it increases the value, summing the better of the two and counting how many nodes we chose to flip.

If that count is even, the configuration is reachable and we are done. If it is odd, we must add or remove exactly one flip to restore even parity, and we want the cheapest adjustment.

The cheapest fix is to give up the smallest gain we made, or absorb the smallest loss we avoided — both equal the minimum of |x XOR k - x| over all nodes. Subtracting that one min_delta repairs parity at minimal cost.

Example: nums = [1,2,1], k = 3. The XORs are 1^3=2, 2^3=1, 1^3=2. Greedily we'd flip nodes 0 and 2 (gains) for sum 2+2+2 = 6, and that flip count (2) is even, so the answer is 6.

Time: O(n) Space: O(1)