Find the Maximum Sum of Node Values

Hard

#2724Time: 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).2 companies

Patterns

Dynamic Programming Greedy Bit Manipulation

Algorithms

Sorting

Data structures

Array Tree

Companies

Deutsche Bank BlackRock

Prompt

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] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i 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:

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:

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:

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 * 10⁴
1 <= k <= 10⁹
0 <= nums[i] <= 10⁹
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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    private List<List<Integer>> adj;3    private int[] nums;4    private int k;5 6    public long maximumValueSum(int[] nums, int k, int[][] edges) {7        this.nums = nums;8        this.k = k;9        int n = nums.length;10        this.adj = new ArrayList<>();11        for (int i = 0; i < n; i++) {12            adj.add(new ArrayList<>());13        }14        for (int[] edge : edges) {15            adj.get(edge[0]).add(edge[1]);16            adj.get(edge[1]).add(edge[0]);17        }18 19        long[] result = dfs(0, -1);20        return result[0];21    }22 23    // Returns a pair [max_sum_even_flips, max_sum_odd_flips]24    private long[] dfs(int u, int p) {25        // dp[0]: max sum for subtree with even number of flipped nodes26        // dp[1]: max sum for subtree with odd number of flipped nodes27        long[] dp = new long[]{(long)nums[u], (long)(nums[u] ^ k)};28 29        for (int v : adj.get(u)) {30            if (v == p) {31                continue;32            }33            long[] childDp = dfs(v, u);34            long currentEven = dp[0];35            long currentOdd = dp[1];36 37            // Combine with child's result38            // To get even flips in total: (even from u + even from v) or (odd from u + odd from v)39            dp[0] = Math.max(currentEven + childDp[0], currentOdd + childDp[1]);40            // To get odd flips in total: (even from u + odd from v) or (odd from u + even from v)41            dp[1] = Math.max(currentEven + childDp[1], currentOdd + childDp[0]);42        }43        return dp;44    }45}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public long maximumValueSum(int[] nums, int k, int[][] edges) {3        long totalSum = 0;4        int count = 0;5        long minAbsDiff = Long.MAX_VALUE;6 7        for (int num : nums) {8            long flippedNum = (long)num ^ k;9            if (flippedNum > num) {10                totalSum += flippedNum;11                count++;12            } else {13                totalSum += num;14            }15            minAbsDiff = Math.min(minAbsDiff, Math.abs((long)num - flippedNum));16        }17 18        if (count % 2 == 0) {19            return totalSum;20        } else {21            return totalSum - minAbsDiff;22        }23    }24}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1public class Solution {2    public long MaximumValueSum(int[] nums, int k, int[][] edges) {3        long f0 = 0, f1 = -0x3f3f3f3f;4        foreach(int x in nums) {5            long tmp = f0;6            f0 = Math.Max(f0 + x, f1 + (x ^ k));7            f1 = Math.Max(f1 + x, tmp + (x ^ k));8        }9        return f0;10    }11}

1class 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 ; } }

1class 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 ); } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem