Watch 10 video solutions for Find the Maximum Sum of Node Values, a hard level problem involving Array, Dynamic Programming, Greedy. This walkthrough by NeetCodeIO has 17,399 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[u, v] connecting the nodes u and v, and update their values as follows:
nums[u] = nums[u] XOR knums[v] = nums[v] XOR kReturn 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 * 1041 <= k <= 1090 <= nums[i] <= 109edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edges represent a valid tree.Problem Overview: You are given a tree where each node has a value. An operation selects an edge and XORs both endpoint values with k. Perform any number of operations to maximize the total sum of node values. The key constraint is that every operation affects two nodes simultaneously.
Approach 1: Brute Force Edge Operation Simulation (Exponential Time)
The most direct way is to try every possible combination of XOR operations on edges. Each operation flips two node values using value ^ k, so different sequences of operations produce different states. A brute-force solution explores these states recursively or via bitmask simulation and computes the resulting sum for each configuration. The state space grows exponentially because each edge can be toggled multiple times. This leads to roughly O(2^n) time in the worst case with O(n) space for recursion or state tracking. It demonstrates the operation behavior but becomes infeasible for large trees.
Approach 2: Greedy Gain Selection with Parity Constraint (O(n) time)
The key observation: applying the XOR operation on edges effectively toggles node values in pairs. That means the number of nodes whose value changes must always be even. For each node, compute the gain if XOR is applied: gain = (nums[i] ^ k) - nums[i]. This transforms the problem into choosing a subset of nodes to flip such that the total gain is maximized while the number of chosen nodes remains even.
Iterate through the array and add all positive gains because they increase the total sum. Track the count of chosen nodes and also keep the smallest absolute gain difference. If the count of positive gains is even, the result is simply the base sum plus all positive gains. If the count is odd, adjust by either removing the smallest positive gain or including the least harmful negative gain. This greedy evaluation works because each node decision is independent except for the global even-parity constraint.
The algorithm runs in O(n) time and O(1) extra space while scanning the array once. Although the input includes a tree, the structure does not affect the final decision because any pair of nodes can effectively be toggled through edge operations. The reasoning combines bit manipulation (using XOR) with a parity-style dynamic programming insight.
Recommended for interviews: The greedy parity approach is what interviewers expect. It shows you recognized the hidden constraint that operations affect nodes in pairs and converted the tree problem into a gain-selection problem. Mentioning the brute-force idea first demonstrates understanding of the operation mechanics, while deriving the O(n) greedy solution shows strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Edge Simulation | O(2^n) | O(n) | Conceptual understanding of how edge XOR operations affect node states |
| Greedy Gain Selection with Parity Constraint | O(n) | O(1) | Optimal solution for large inputs; handles the even-toggle constraint efficiently |