Find the maximum sum of node values

Array Dynamic Programming Greedy Bit Manipulation Tree Sorting

69.5% acceptance

Feb 25, 2026

919

133

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, and a positive integer k, and a 0-indexed array of non-negative integers nums of length n. Alice wants the sum of values of tree nodes to be maximum. She can XOR any edge's endpoints any number of times. Return the maximum possible sum of the values Alice can achieve.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_value_sum(nums: Vec<i32>, k: i32, _edges: Vec<Vec<i32>>) -> i64 {
    // Each XOR operation on an edge (u,v) flips both u and v.
    // Net effect: we can flip an even number of nodes (flip a node = xor with k).
    // For each node, gain = (nums[i] ^ k) - nums[i]. If gain > 0, we want to flip.
    // We can flip any even number of nodes.
    let mut gains: Vec<i64> = nums.iter().map(|&x| (x ^ k) as i64 - x as i64).collect();
    let base: i64 = nums.iter().map(|&x| x as i64).sum();
    gains.sort_by(|a, b| b.cmp(a));
    let mut total = base;
    let mut i = 0;
    while i + 1 < gains.len() {
      if gains[i] + gains[i+1] > 0 {
        total += gains[i] + gains[i+1];
        i += 2;
      } else { break; }
    }
    total
  }
}