[C++] XOR Again If Needed (Greedy)
Intuition\n Describe your first thoughts on how to solve this problem. \n- Apply max(nums[i], nums[i] ^ k) for each element in the array\n- We can always change
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Apply `max(nums[i], nums[i] ^ k)` for each element in the array\n- We can always change the even number of times because this is a tree\n- If we changed the odd number of times, we need to XOR an integer again\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- find the number of changes and the maximum sum\n- if the number of changes is even, we can submit the sum directly\n- if the number of changes is odd, we need to pick one of the integers in the array to XOR it again\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 {\npublic:\n    // time/space: O(n)/O(1)\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        // find the number of changes and the maximum sum\n        int change = 0;\n        long long sum = 0LL;\n        for (auto& num : nums) {\n            if ((num ^ k) > num) {\n                change++;\n                sum += (num ^ k);\n            }\n            else {\n                sum += num;\n            }\n        }\n        \n        // if the number of changes is even, we can submit the sum directly\n        if ((change & 1) == 0) return sum;\n        \n        // if the number of changes is odd, we need to pick one of the integers in the array to XOR it again\n        long long maxSum = 0LL;\n        for (int i = 0; i < nums.size(); i++) {\n            maxSum = max(maxSum, sum - abs(nums[i] - (nums[i] ^ k)));\n        }\n        return maxSum;\n    }\n};\n```
['Greedy', 'Bit Manipulation', 'Tree', 'C++']