3068. Find the Maximum Sum of Node Values
Hard
There exists an undirected tree with n
nodes numbered 0
to n  1
. You are given a 0indexed 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 0indexed array of nonnegative 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 nodesu
andv
, 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^{4}
1 <= k <= 10^{9}
0 <= nums[i] <= 10^{9}
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.
Solution:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @param Integer[][] $edges
* @return Integer
*/
function maximumValueSum($nums, $k, $edges) {
$maxSum = 0;
$changedCount = 0;
$minChangeDiff = PHP_INT_MAX;
foreach ($nums as $num) {
$maxSum += max($num, $num ^ $k);
$changedCount += (($num ^ $k) > $num) ? 1 : 0;
$minChangeDiff = min($minChangeDiff, abs($num  ($num ^ $k)));
}
if ($changedCount % 2 == 0)
return $maxSum;
return $maxSum  $minChangeDiff;
}
}
Contact Links
Top comments (1)
Does the solution take into account all the potential edge cases where multiple operations might be required? This was a very informative read, thanks!