Find the Maximum Sum of Node Values - Practice Coding Problems

Find the Maximum Sum of Node Values - Problem

Array Dynamic Programming Greedy Bit Manipulation Tree Sorting Hard

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.

Input & Output

Example 1 — Basic Tree

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

› Output: 8

💡 Note: XOR nodes 0 and 2 with k=3: nums becomes [2,2,2]. Original sum was 4, new sum is 6. Wait, let me recalculate: 1^3=2, 2^3=1, 1^3=2. If we XOR edge [0,2] we can't directly do that since they're not connected. We can XOR edge [0,1] to get [2,1,1] sum=4, then XOR [0,2] indirectly. Actually, we can achieve [2,2,2] by XORing both edges, giving sum = 8.

Example 2 — Single Node

$ Input: nums = [2], k = 5, edges = []

› Output: 7

💡 Note: Single node: choose max(2, 2^5) = max(2, 7) = 7

Example 3 — No Benefit

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

› Output: 21

💡 Note: 7^3=4 for all nodes, so XOR reduces values. Keep original: 7+7+7=21

Constraints

2 ≤ nums.length ≤ 2 * 10⁴
1 ≤ k ≤ 10⁹
0 ≤ nums[i] ≤ 10⁹
edges.length == nums.length - 1
edges[i].length == 2
0 ≤ edges[i][0], edges[i][1] ≤ nums.length - 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with nodes and their values, plus XOR key k

XOR Operations

Apply XOR k to connected nodes via edges

Maximized Sum

Find configuration that gives highest total sum

Key Takeaway

🎯 Key Insight: XOR operations have parity constraints in trees - select even number of highest-benefit transformations

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that XOR operations on tree edges create parity constraints - we need an even number of node transformations. The optimal approach calculates XOR benefits for each node independently, sorts them, and selects the maximum even-sized subset. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Maximize Individual Benefits	O(n log n)	O(n)	Calculate XOR benefit for each node and greedily select improvements
Optimal - XOR Parity Analysis	O(n log n)	O(n)	Use XOR properties and parity constraints to find the optimal solution directly
Brute Force - Try All Combinations	O(2^(n²))	O(n)	Try every possible combination of XOR operations on edges

Greedy - Maximize Individual Benefits — Algorithm Steps

Calculate XOR benefit for each node
Sort nodes by descending benefit
Apply XOR to nodes with positive benefit
Handle parity constraints for valid tree operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Benefits

Find XOR benefit for each node

Sort by Benefit

Order nodes by descending benefit

Select Greedily

Choose nodes with positive benefits (respecting parity)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int value;
    int index;
} Benefit;

int compareBenefits(const void* a, const void* b) {
    Benefit* ba = (Benefit*)a;
    Benefit* bb = (Benefit*)b;
    return bb->value - ba->value;  // Descending order
}

long long solution(int* nums, int numsSize, int k, int edges[][2], int edgesSize) {
    int n = numsSize;
    if (n == 1) {
        int xor_val = nums[0] ^ k;
        return nums[0] > xor_val ? nums[0] : xor_val;
    }
    
    // Calculate benefit for each node if XORed
    Benefit* benefits = malloc(n * sizeof(Benefit));
    for (int i = 0; i < n; i++) {
        benefits[i].value = (nums[i] ^ k) - nums[i];
        benefits[i].index = i;
    }
    
    // Sort by benefit in descending order
    qsort(benefits, n, sizeof(Benefit), compareBenefits);
    
    long long totalSum = 0;
    for (int i = 0; i < n; i++) {
        totalSum += nums[i];
    }
    
    int countPositive = 0;
    
    // Greedily add positive benefits
    for (int i = 0; i < n; i++) {
        if (benefits[i].value > 0) {
            totalSum += benefits[i].value;
            countPositive++;
        } else {
            break;
        }
    }
    
    // Handle parity constraint
    if (countPositive % 2 == 1) {
        long long minCost = LLONG_MAX;
        
        // Option 1: Remove smallest positive benefit
        if (countPositive > 0) {
            long long smallestPositive = benefits[countPositive - 1].value;
            if (smallestPositive < minCost) {
                minCost = smallestPositive;
            }
        }
        
        // Option 2: Add largest negative benefit
        for (int i = countPositive; i < n; i++) {
            if (benefits[i].value < 0) {
                long long cost = -benefits[i].value;
                if (cost < minCost) {
                    minCost = cost;
                }
                break;
            }
        }
        
        if (minCost != LLONG_MAX) {
            totalSum -= minCost;
        }
    }
    
    free(benefits);
    return totalSum;
}

int main() {
    int nums[] = {1, 2, 1};
    int edges[][2] = {{0, 1}, {0, 2}};
    int k = 3;
    
    long long result = solution(nums, 3, k, edges, 2);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting nodes by benefit takes O(n log n), other operations are O(n)

⚡ Linearithmic

Space Complexity

O(n)

Additional array to store benefit values for each node

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Maximize Individual Benefits — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler