# Find the Maximum Sum of Node Values
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-maximum-sum-of-node-values)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-sum-of-node-values
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Tree
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [BlackRock](https://scaleengineer.com/companies/blackrock)
---
## Problem
There exists an **undirected** tree with `n` nodes numbered `0` to `n - 1`. You are given a **0-indexed** 2D integer array `edges` of length `n - 1`, where `edges[i] = [ui, vi]` indicates that there is an edge between nodes `ui` and `vi` in the tree. You are also given a **positive** integer `k`, and a **0-indexed** array of **non-negative** integers `nums` of length `n`, where `nums[i]` represents the **value** of the node numbered `i`.

Alice wants the sum of values of tree nodes to be **maximum**, for which Alice can perform the following operation **any** number of times (**including zero**) on the tree:

* Choose any edge `[u, v]` connecting the nodes `u` and `v`, and update their values as follows:  
  * `nums[u] = nums[u] XOR k`
  * `nums[v] = nums[v] XOR k`

Return _the **maximum** possible **sum** of the **values** Alice can achieve by performing the operation **any** number of times_.

**Example 1:**

![](https://assets.glich.co/dsa/find-the-maximum-sum-of-node-values/image0.png) 

**Input:** nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
**Output:** 6
**Explanation:** 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:**

![](https://assets.glich.co/dsa/find-the-maximum-sum-of-node-values/image1.png) 

**Input:** nums = [2,3], k = 7, edges = [[0,1]]
**Output:** 9
**Explanation:** 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:**

![](https://assets.glich.co/dsa/find-the-maximum-sum-of-node-values/image2.png) 

**Input:** nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
**Output:** 42
**Explanation:** 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.

# Approaches
## Tree Dynamic Programming
This approach uses dynamic programming on the tree structure. The core idea is that for any subtree, we want to find the maximum possible sum of node values, considering two scenarios: one where an even number of nodes in the subtree are "flipped" (their value is XORed with `k`), and one where an odd number of nodes are flipped. This information allows a parent node to make decisions by combining results from its children's subtrees.
**Time:** O(N) where N is the number of nodes. We visit each node and edge once during the DFS. · **Space:** O(N) for the adjacency list and the recursion stack depth in the worst case (for a skewed tree).
**Pros:** It's a standard and structured way to solve problems on trees.; It correctly models the constraints of the problem.
**Cons:** Requires building a graph and performing a traversal, which is more complex than necessary.; Uses O(N) auxiliary space, which is less optimal than the greedy approach.
### Explanation
First, we build an adjacency list representation of the tree from the `edges` array. We then perform a Depth First Search (DFS) from an arbitrary root (e.g., node 0). The DP state for a node `u` will be a pair of values: `dp[u] = [max_sum_even, max_sum_odd]`, representing the maximum sum in the subtree of `u` with an even or odd number of flipped nodes, respectively. The DFS function computes this state in a post-order fashion. For a leaf, the state is simply `[nums[u], nums[u] XOR k]`. For an internal node, it initializes its state similarly and then iteratively combines the results from its children's subtrees. To combine a child's result, we calculate the new `max_sum_even` by taking the maximum of (current even + child even) and (current odd + child odd). A similar calculation is done for `max_sum_odd`. After the DFS completes, the answer is the `max_sum_even` for the root node, as the total number of flips in the entire tree must be even.

```java
class Solution {
    private List<List<Integer>> adj;
    private int[] nums;
    private int k;

    public long maximumValueSum(int[] nums, int k, int[][] edges) {
        this.nums = nums;
        this.k = k;
        int n = nums.length;
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        long[] result = dfs(0, -1);
        return result[0];
    }

    // Returns a pair [max_sum_even_flips, max_sum_odd_flips]
    private long[] dfs(int u, int p) {
        // dp[0]: max sum for subtree with even number of flipped nodes
        // dp[1]: max sum for subtree with odd number of flipped nodes
        long[] dp = new long[]{(long)nums[u], (long)(nums[u] ^ k)};

        for (int v : adj.get(u)) {
            if (v == p) {
                continue;
            }
            long[] childDp = dfs(v, u);
            long currentEven = dp[0];
            long currentOdd = dp[1];

            // Combine with child's result
            // To get even flips in total: (even from u + even from v) or (odd from u + odd from v)
            dp[0] = Math.max(currentEven + childDp[0], currentOdd + childDp[1]);
            // To get odd flips in total: (even from u + odd from v) or (odd from u + even from v)
            dp[1] = Math.max(currentEven + childDp[1], currentOdd + childDp[0]);
        }
        return dp;
    }
}
```
### Algorithm
*   First, build an adjacency list representation of the tree from the `edges` array.
*   We perform a Depth First Search (DFS) from an arbitrary root (e.g., node 0).
*   The DP state for a node `u` will be a pair of values: `dp[u] = [max_sum_even, max_sum_odd]`.
    *   `max_sum_even`: The maximum sum achievable in the subtree rooted at `u`, given that an even number of nodes in this subtree have their values flipped.
    *   `max_sum_odd`: The maximum sum achievable in the subtree rooted at `u`, given that an odd number of nodes in this subtree have their values flipped.
*   The DFS function, say `dfs(u, parent)`, will compute `dp[u]` using a post-order traversal.
*   **Base Case (Leaf Node):** For a leaf node `u`, there are no subtrees to combine. We only consider flipping `u` itself.
    *   If we don't flip `u` (0 flips, which is even), the sum is `nums[u]`. So, `max_sum_even = nums[u]`.
    *   If we flip `u` (1 flip, which is odd), the sum is `nums[u] XOR k`. So, `max_sum_odd = nums[u] XOR k`.
*   **Recursive Step (Internal Node):** For an internal node `u`, we first initialize its DP values as if it were a leaf: `dp[u] = [nums[u], nums[u] XOR k]`. Then, we iterate through each child `v` of `u`. For each child, we recursively call `dfs(v, u)` to get `dp[v] = [child_even_sum, child_odd_sum]`. We then combine this result with `u`'s current accumulated DP values.
    *   Let `current_even_sum` and `current_odd_sum` be the DP values for `u` accumulated so far (from `u` itself and previously processed children).
    *   To get a new total even number of flips, we can either combine an even number of flips from `u`'s part with an even number from `v`'s subtree, OR an odd number from `u`'s part with an odd number from `v`'s subtree.
    *   `new_even_sum = max(current_even_sum + child_even_sum, current_odd_sum + child_odd_sum)`
    *   Similarly, for an odd number of flips:
    *   `new_odd_sum = max(current_even_sum + child_odd_sum, current_odd_sum + child_even_sum)`
    *   We update `dp[u]` with these new values and proceed to the next child.
*   After the DFS completes for the root, `dp[root][0]` will hold the answer. This is because for the entire tree, the total number of nodes we are allowed to flip must be even.

## Greedy with Parity Correction
This approach is based on a key observation about the nature of the operations. Applying an operation on an edge `(u, v)` is equivalent to flipping the states of `u` and `v`. By applying a sequence of operations along a path between two nodes `i` and `j`, we can flip the states of just `i` and `j`. This means we can flip any pair of nodes. Consequently, we can flip any set of nodes as long as the total number of flipped nodes is even. The problem then simplifies to a greedy choice for each node, with a final correction step if our greedy choices lead to an odd number of flips.
**Time:** O(N) for a single pass through the `nums` array. · **Space:** O(1) as we only use a few variables to store the running sum, count, and minimum difference.
**Pros:** Extremely efficient in both time and space.; Simple to understand and implement once the core insight is grasped.; Ignores the `edges` data entirely, simplifying the logic.
**Cons:** The core insight that the graph structure allows any even number of nodes to be flipped is not immediately obvious and requires some graph theory reasoning.
### Explanation
The core insight is that the tree structure guarantees we can flip any two nodes `i` and `j` by applying the operation on all edges along the unique path between them. This is because intermediate nodes on the path are part of two operations, so their values are XORed twice, canceling the effect (`val XOR k XOR k = val`). Only the endpoints `i` and `j` are flipped. Since we can flip any pair of nodes, we can achieve any configuration where an even number of nodes are flipped. The problem then becomes: for each node `i`, we can either keep its value `nums[i]` or change it to `nums[i] XOR k`. We should greedily choose the larger of the two values for each node to maximize the sum. We calculate this greedy sum and count how many nodes we 'flipped' (where `nums[i] XOR k > nums[i]`). If this count is even, our greedy sum is the answer. If the count is odd, our choice is invalid. To fix this, we must make one change: either un-flip a profitably flipped node or flip an unprofitably unflipped node. To minimize the reduction in sum, we should make the change that has the smallest impact. This is equivalent to finding the node `i` with the minimum `abs(nums[i] - (nums[i] XOR k))`. We subtract this minimum absolute difference from our greedy sum to get the final answer.

```java
class Solution {
    public long maximumValueSum(int[] nums, int k, int[][] edges) {
        long totalSum = 0;
        int count = 0;
        long minAbsDiff = Long.MAX_VALUE;

        for (int num : nums) {
            long flippedNum = (long)num ^ k;
            if (flippedNum > num) {
                totalSum += flippedNum;
                count++;
            } else {
                totalSum += num;
            }
            minAbsDiff = Math.min(minAbsDiff, Math.abs((long)num - flippedNum));
        }

        if (count % 2 == 0) {
            return totalSum;
        } else {
            return totalSum - minAbsDiff;
        }
    }
}
```
### Algorithm
*   Initialize `total_sum = 0`, `count = 0`, and `min_abs_diff = Long.MAX_VALUE`.
*   Iterate through each value `num` in the `nums` array.
*   Calculate the flipped value: `flipped_num = num XOR k`.
*   If `flipped_num > num`:
    *   Add `flipped_num` to `total_sum`.
    *   Increment `count`.
*   Else:
    *   Add `num` to `total_sum`.
*   Calculate the absolute difference `diff = abs(num - flipped_num)`.
*   Update `min_abs_diff = min(min_abs_diff, diff)`.
*   After the loop, check if `count` is even.
*   If `count` is even, return `total_sum`.
*   If `count` is odd, return `total_sum - min_abs_diff`.

# Solutions
### CSharp

```csharp
public class Solution {
    public long MaximumValueSum(int[] nums, int k, int[][] edges) {
        long f0 = 0, f1 = -0x3f3f3f3f;
        foreach(int x in nums) {
            long tmp = f0;
            f0 = Math.Max(f0 + x, f1 + (x ^ k));
            f1 = Math.Max(f1 + x, tmp + (x ^ k));
        }
        return f0;
    }
}
```

### Java

```java
class Solution { public long maximumValueSum ( int [] nums , int k , int [][] edges ) { long f0 = 0 , f1 = - 0x3f3f3f3f ; for ( int x : nums ) { long tmp = f0 ; f0 = Math . max ( f0 + x , f1 + ( x ^ k )); f1 = Math . max ( f1 + x , tmp + ( x ^ k )); } return f0 ; } }
```

### CPP

```cpp
class Solution { public: long long maximumValueSum ( vector < int >& nums , int k , vector < vector < int >>& edges ) { long long totalSum = 0 ; int count = 0 ; int positiveMin = INT_MAX ; int negativeMax = INT_MIN ; for ( int nodeValue : nums ) { int nodeValAfterOperation = nodeValue ^ k ; totalSum += nodeValue ; int netChange = nodeValAfterOperation - nodeValue ; if ( netChange > 0 ) { positiveMin = min ( positiveMin , netChange ); totalSum += netChange ; count += 1 ; } else { negativeMax = max ( negativeMax , netChange ); } } if ( count % 2 == 0 ) { return totalSum ; } return max ( totalSum - positiveMin , totalSum + negativeMax ); } };
```

### Python

```python
class Solution : def maximumValueSum ( self , nums : List [ int ], k : int , edges : List [ List [ int ]]) -> int : f0 , f1 = 0 , - inf for x in nums : f0 , f1 = max ( f0 + x , f1 + ( x ^ k )), max ( f1 + x , f0 + ( x ^ k )) return f0
```