Skip to main content
Talentd

Find the Maximum Sum of Node Values - Solution & Explanation

HardArrayDynamic ProgrammingGreedyBit Manipulation24 min readAsked at: Meta, Deutsche Bank, BlackRock +1
Practice this problem

Problem Statement

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:

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

Approach Overview

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 1: Brute Force Approach

This approach involves checking all possible operations on each edge and calculating the resulting sum by applying the XOR operation. We must continuously update and evaluate for every operation on each pair of nodes linked by an edge to see if the resulting sum after the operation is beneficial.

This naive strategy will consider 2^n operations (since each edge can have 2 XOR states per pair), making it inefficient for larger datasets. Ideal for understanding XOR effects but not recommended for large n.

This C function calculates the maximum possible sum by performing ARC XOR operations optimally on each edge. The initial sum is calculated, then for each edge, the potential new sum after the operation is checked and updated if beneficial.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes. Each iteration is constant time.
Space Complexity: O(1), since additional space used is constant.

Try this approach in the editor →

Approach 2: Optimized Evaluation

Instead of brute checking each edge operation individually, observe that XOR operation symmetry allows flipping of node values to be optimal only when advantageous. Analyze and preprocess which nodes when XOR'd with k will increase their value and prioritize these changes globally without redundant individual edge checks.

This idea is crucially about observing which nodes independently contribute more value when toggled and using the tree structure to apply XOR operations optimally.

This C code efficiently determines the maximum sum by comparing the original sum to the sum if every node were XOR'd independently with k. This leverages XOR symmetry to quickly evaluate if any operation is beneficial globally.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as it processes each node individually once.
Space Complexity: O(1), using a fixed amount of extra space.

Try this approach in the editor →

Approach 3: Dynamic Programming

For any number x, its value remains unchanged after being XORed with k an even number of times. Therefore, for any path in a tree, if we perform the operation on all edges in the path, the values of all nodes on the path except the start and end nodes will not change.

Additionally, no matter how many operations are performed, there will always be an even number of elements XORed with k, and the remaining elements will remain unchanged.

Thus, the problem is transformed into: for the array nums, select an even number of elements to XOR with k to maximize the sum.

We can use dynamic programming to solve this problem. Let f_0 represent the maximum sum when an even number of elements have been XORed with k, and f_1 represent the maximum sum when an odd number of elements have been XORed with k. The state transition equations are:

$ \begin{aligned} f_0 &= max(f_0 + x, f_1 + (x \oplus k)) \ f_1 &= max(f_1 + x, f_0 + (x \oplus k)) \end{aligned}

where x represents the current element's value.

We traverse the array nums and update f_0 and f_1 according to the above state transition equations. Finally, we return f_0.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n), where n is the number of nodes. Each iteration is constant time.
Space Complexity: O(1), since additional space used is constant.

Optimized Evaluation

Time Complexity: O(n), as it processes each node individually once.
Space Complexity: O(1), using a fixed amount of extra space.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Edge SimulationO(2^n)O(n)Conceptual understanding of how edge XOR operations affect node states
Greedy Gain Selection with Parity ConstraintO(n)O(1)Optimal solution for large inputs; handles the even-toggle constraint efficiently

Video Solution

Find the Maximum Sum of Node Values - Leetcode 3068 - Python • NeetCodeIO • 17,589 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Maximum Sum of Node Values easy or hard?
The problem is rated Hard because the tree structure can mislead you into thinking complex traversal or dynamic programming is required. The real challenge is recognizing that XOR operations affect nodes in pairs, creating an even-parity constraint that leads to a greedy O(n) solution.
Find the Maximum Sum of Node Values Python/Java solution
Python and Java implementations follow the same logic: compute the base sum, calculate gain = (nums[i] ^ k) - nums[i], accumulate positive gains, and track the minimum absolute gain adjustment. The algorithm uses a single loop and constant extra memory, giving O(n) time complexity.
How to solve Find the Maximum Sum of Node Values in O(n)?
Compute the base sum of all node values. For each node, calculate the gain from applying XOR with k. Add every positive gain while counting how many nodes are flipped. If the count is even, keep the sum. If the count is odd, subtract the smallest absolute gain difference to restore even parity. This single pass achieves O(n) time.
What is the best approach for Find the Maximum Sum of Node Values?
The optimal approach uses a greedy gain calculation with an even-parity constraint. Compute the gain for flipping each node using (nums[i] ^ k) - nums[i], add all positive gains, and ensure the number of flipped nodes is even. If it becomes odd, adjust by removing the smallest positive gain or adding the least negative gain. This runs in O(n) time and O(1) space.
Is Find the Maximum Sum of Node Values asked at Google/Amazon/Meta?
Problems combining XOR operations, greedy selection, and tree reasoning frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test whether candidates recognize parity constraints or convert structural problems into simpler array optimizations.
What data structure is used in Find the Maximum Sum of Node Values?
The main data structure is a simple array storing node values. The tree structure is provided through edges but does not require traversal in the optimal solution. The logic focuses on XOR bit manipulation and greedy gain selection rather than traditional tree traversal.
What is the time complexity of Find the Maximum Sum of Node Values?
The optimal solution runs in O(n) time because it scans the node values once to compute XOR gains and track parity adjustments. Space complexity is O(1) since only a few variables are required. Brute-force approaches that simulate operations can grow exponentially and are not practical for large inputs.

Ready to solve this problem?

Practice Find the Maximum Sum of Node Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Number of Coins to Place in Tree Nodes

Next

Maximum Score After Applying Operations on a Tree