Count Number of Changed Nodes || C++, C, Python, Java
Approach\n Describe your approach to solving the problem. \nSince the graph we\'re given is connected, undirected and acyclic, there is a path between any two n
# Approach\n<!-- Describe your approach to solving the problem. -->\nSince the graph we\'re given is connected, undirected and acyclic, there is a path between any two nodes in the graph. Moreover, because of the properties of the XOR operation, any nodes in the path between node `u` and node `v` will remain the same since `x XOR x = x`. Thus we can treat each node independently and disregard the `edges`. \n\nTherefore, we can solve this by maintaining a `sum` where we would add the `max(nums[i] ^ k, nums[i])` in each iteration of a loop. However, another since in each operation we need to change an even number of nodes, we need to make sure that the number of nodes we change (to its higher XOR value) is even. We can do this by using `count` to sum the number of times we do an operation. Lastly, we will also use `minDiff` to keep track of the minimum absolute change between a node and its XOR value so that if we need to change a node in the end because of `count` being odd, then we can make the minimum change necessary.\n\nIn the end return `sum` and subtract `minDiff` from it if `count` is odd, which will represent changing a node back to its original value to balance out the number of operations.\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```C++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        long long sum = 0, count = 0, minDiff = INT_MAX;\n        for (long long num : nums){\n            sum += max(num ^ k, num);\n            count += (num ^ k) > num;\n            minDiff = min(minDiff, abs(num - (num ^ k)));\n        }\n        return sum - (count % 2 ? minDiff : 0);\n    }\n};\n```\n```C []\nlong long maximumValueSum(int* nums, int numsSize, int k, int** edges, int edgesSize, int* edgesColSize) {\n    long long res = 0, count = 0, minDiff = 1 << 30;\n    for (int i = 0; i < numsSize; i++){\n        int curr = nums[i] ^ k;\n        res += (curr > nums[i]) ? curr : nums[i];\n        count += (curr > nums[i]);\n        minDiff = (minDiff < abs(nums[i] - curr)) ? minDiff : abs(nums[i] - curr);\n    }\n    return res - (count % 2 ? minDiff : 0);\n}\n```\n```python3 []\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        sum, count, minDiff = 0, 0, float(\'inf\')\n        for num in nums:\n            sum += max(num ^ k, num)\n            count += (num ^ k > num)\n            minDiff = min(minDiff, abs(num - (num ^ k)))\n        return sum - (minDiff if count % 2 else 0)\n```\n```Java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        long sum = 0, count = 0, minDiff = Integer.MAX_VALUE;\n        for (long num : nums){\n            sum += Math.max(num ^ k, num);\n            count += ((num ^ k) > num) ? 1 : 0;\n            minDiff = Math.min(minDiff, Math.abs(num - (num ^ k)));\n        }\n        return sum - (count % 2 == 1 ? minDiff : 0);\n    }\n}\n```\n
['Array', 'Dynamic Programming', 'Greedy', 'Tree', 'C', 'Sorting', 'Python', 'C++', 'Java', 'Python3']