Find the Maximum Sum of Node Values
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve the problem of finding the maximum sum of values in the nums array after perfo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem of finding the maximum sum of values in the nums array after performing at most one XOR operation per element with a given integer k, we can break down the solution into a few key steps:\n1. XOR Operation: Understand how the XOR operation affects the numbers. XORing a number with k can either increase or decrease the value depending on the bits.\n2. Maximizing Sum: For each number in the array, decide whether to apply the XOR operation to maximize the overall sum.\n3. Handling Odd Changes: If the number of changes (XOR operations that increase the value) is odd, we might need to adjust the sum by potentially removing the smallest beneficial change to make it even, thereby ensuring the sum is optimal.1\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Iterate Over Array: Loop through each element in the nums array and calculate the potential new value after applying the XOR operation with k.\n2. Track Changes: Maintain a count of how many changes (XOR operations) actually increase the value.\n3. Track Minimum Change Difference: Keep track of the smallest difference between the original and XORed value for potential adjustment if the number of beneficial changes is odd.\n4. Adjust Final Sum: If the number of beneficial changes is odd, subtract the smallest difference from the total sum to ensure the final sum is maximized.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n public:\n  long long maximumValueSum(vector<int>& nums, int k,\n                            vector<vector<int>>& edges) {\n    long long maxSum = 0;\n    int changedCount = 0;\n    int minChangeDiff = INT_MAX;\n\n    for (const int num : nums) {\n      maxSum += max(num, num ^ k);\n      changedCount += ((num ^ k) > num) ? 1 : 0;\n      minChangeDiff = min(minChangeDiff, abs(num - (num ^ k)));\n    }\n\n    if (changedCount % 2 == 0)\n      return maxSum;\n    return maxSum - minChangeDiff;\n  }\n};\n```
['Array', 'Dynamic Programming', 'Greedy', 'Bit Manipulation', 'Tree', 'Sorting']