Find the Maximum Sum of Node Values

The key observation in Find the Maximum Sum of Node Values is that every operation flips exactly two endpoints, so the final set of XOR-changed nodes must have even size. That turns the tree operation into a parity optimization problem over per-node gains. Once you compute each node's benefit from applying XOR with k, the best answer is either taking all positive gains with even count or dropping the smallest adjustment needed to fix odd parity.

Problem Statement

You are given a tree where each node has a non-negative value, and one operation lets you pick an edge and replace both endpoint values with their value XOR k. Because the graph is a tree, the edge layout looks important at first, but the real restriction comes from how many nodes end up toggled after all operations.

Your goal is to maximize the total sum of node values after performing any number of these edge operations. A useful way to restate the problem is this: decide which nodes should switch from nums[i] to nums[i] XOR k, under the rule that the total number of switched nodes must be even. That parity rule is why a naive choose-every-profitable-node strategy fails on cases where the number of profitable flips is odd.

Examples

Example 1

Input: nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]

Output: 6

Alice can achieve the maximum sum of 6 using a single operation:

• Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -> [2,2,2]. The total sum of values is 2 + 2 + 2 = 6. It can be shown that 6 is the maximum achievable sum of values.

Example 2

Input: nums = [2,3], k = 7, edges = [[0,1]]

Output: 9

Alice can achieve the maximum sum of 9 using a single operation:

• Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -> [5,4]. The total sum of values is 5 + 4 = 9. It can be shown that 9 is the maximum achievable sum of values.

Example 3

Input: nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]

Output: 42

The maximum achievable sum is 42 which can be achieved by Alice performing no operations.

Constraints

• 2 <= n == nums.length <= 2 * 104
• 1 <= k <= 109
• 0 <= nums[i] <= 109
• edges.length == n - 1
• edges[i].length == 2
• 0 <= edges[i][0], edges[i][1] <= n - 1
• The input is generated such that edges represent a valid tree.

Solution Approach

Convert edge operations into an even-parity selection problem

For each node, compare keeping nums[i] versus changing it to nums[i] XOR k. The gain is (nums[i] XOR k) - nums[i]. Although operations happen on edges, repeated path operations let you realize any even-sized set of toggled nodes in a tree. That means the tree structure only guarantees feasibility of even parity, so the problem reduces to choosing an even number of node gains to add.

Take all positive gains, then repair odd parity

Start from the base sum of nums. Add every positive gain, because each such node individually improves the total. The catch is parity: if the count of chosen positive gains is odd, that state is unreachable. Fix it by either removing the smallest positive gain you included or adding the least harmful non-positive gain you skipped. Choose the better of those two parity repairs.

View it as two-state dynamic programming

You can also track dpEven and dpOdd while scanning nodes, where each state stores the best extra gain achievable with an even or odd number of chosen flips so far. For each gain g, either skip it or take it and swap parity. This DP explains why the greedy parity-fix works: only the best even-parity total matters at the end, and the tree edges never need explicit traversal once parity is understood.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The solution runs in O(n) time because you evaluate each node once and update either simple parity bookkeeping or a two-state DP. It uses O(1) extra space beyond the input because you only store the running sum, parity information, and a few best adjustment values. Even though the input is a tree, no adjacency traversal is required after recognizing that the only surviving constraint is an even number of XOR-changed nodes.

What Interviewers Usually Probe

• They want you to notice that edge operations do not require tree DP over children; the tree only enforces even toggle parity.
• A strong solution quickly rewrites the problem from modifying edges to selecting node-wise XOR gains under an even-count constraint.
• If you mention rooting the tree, the useful conclusion is feasibility of any even-sized toggled set, not a full binary-tree recurrence.

Common Pitfalls or Variants

Common pitfalls

• Greedily taking every node where nums[i] XOR k is larger than nums[i] without checking whether that chosen count is odd.
• Building a full traversal-based DP on the tree and overcomplicating a problem whose final state depends only on parity of toggled nodes.
• Assuming the exact edge sequence matters for the maximum sum, when only the reachable even-cardinality set of changed nodes matters.

Follow-up variants

• Return the actual set of nodes to toggle instead of only the maximum sum, which requires reconstructing the parity choice.
• Replace the tree with a general connected graph; the same even-parity reachability idea still drives the optimization.
• Ask for the maximum sum after exactly m operations, which changes the simple parity view into a tighter operation-count constraint.

FAQ

What is the main trick in Find the Maximum Sum of Node Values?

The main trick is proving that the tree operations are equivalent to choosing an even number of nodes to apply XOR with k. Once you convert each node into a gain value, the problem becomes maximizing total gain under even parity.

Why can I ignore the exact tree shape?

Because on a tree, combining edge operations along paths lets you toggle endpoints while intermediate effects cancel in pairs. The result is that any even-sized set of nodes is achievable, so the structure matters only for that feasibility fact.

Is this really a binary-tree traversal and state tracking problem?

It can be framed that way if you root the tree and reason about parity states, but the optimal implementation does not need an actual traversal. The important state is even versus odd count of chosen XOR gains, which collapses the tree into a two-state optimization.

Why does taking all positive gains sometimes give the wrong answer?

Because the number of chosen positive-gain nodes might be odd, and an odd number of toggled nodes cannot be produced by operations that always affect two endpoints. You must repair parity by sacrificing the smallest positive gain or accepting the least harmful non-positive gain.

What are the best time and space bounds for LeetCode 3068?

You can solve it in O(n) time and O(1) extra space. Each node contributes one gain calculation, and you only need running totals plus the best parity adjustment values.