✅All 4 approach explained || Detailed explanation ever available on internet || Must watch Sol✨
\n# Overview\n\nWe aim to maximize the sum of values of all nodes in an undirected tree by performing a specific operation.  \nThe operation allows us to replac
\n# Overview\n\nWe aim to maximize the sum of values of all nodes in an undirected tree by performing a specific operation.  \nThe operation allows us to replace the values of any two **adjacent** nodes with their XOR values, with a given integer `k`.\n\n**Key Observations:**\n\n1. Alice can perform an operation on any edge `[u, v]` by XOR-ing the values of nodes `u` and `v` with a positive integer `k`.\n2. Alice wants to maximize the sum of the values of the tree nodes. This means she aims to maximize the total value represented by the sum of individual node values after performing the specified operations.\n3. Alice can perform the operation any number of times (including zero) on the tree. This implies she can selectively choose edges and perform the XOR operation to maximize the sum of node values.\n\n> **Note:** The XOR (exclusive OR) operator compares corresponding bits of two operands and returns 1 if the bits are different and 0 if they are the same. For instance, in binary 1010XOR1100=01101010 XOR 1100 = 01101010XOR1100\\=0110 indicating that the second and third bits differ while the first and fourth bits are the same.  \n> Bitwise XOR operation is commutative and associative. That means aXORbXORb=aa XOR b XOR b = aaXORbXORb\\=a, and aXORb=bXORaa XOR b = b XOR aaXORb\\=bXORa. Hence, the order of applying XOR operations doesn\'t matter.  \n> XORing a number with itself (aXORaa XOR aaXORa) results in 000. Therefore, performing the XOR operation twice on the same number yields the original number.\n\n---\n\n### Approach 1: Top-Down Dynamic Programming - Memoization\n\n#### Intuition\n\nLet\'s assume we want to replace the values of any two arbitrary nodes `U` and `V` with their XOR values, where `U` and `V` are not adjacent. Since, the tree is connected, undirected, and acyclic, there always exists a path between `U` and `V`. Let\'s assume the length of this path is `L` and P={P1,P2,P3...PL\u22121}P =\\\\{P\\_1, P\\_2, P\\_3...P\\_{L-1}\\\\}P\\={P1\u200B,P2\u200B,P3\u200B...PL\u22121\u200B} denotes the set of nodes on this path, following the order in which they appear on the path from `U` to `V`. Below is a diagram for better understanding:\n\n![image.png](../Figures/3068/3068_path.png)\n\nNow, let\'s operate on every edge from `U` to `V`. Since, there are exactly `L` edges between both the nodes, we will be performing `L` operations in total.\n\nThe value of each node after these `L` operations will change as shown below:\n\n![image.png](../Figures/3068/3068_path_xor.png)\n\nSince the XOR operation obeys the properties of commutativity and identity, A\u2005\u200AXOR\u2005\u200AB\u2005\u200AXOR\u2005\u200AB=AA\\\\; XOR\\\\; B\\\\; XOR\\\\; B = AAXORBXORB\\=A for any two integers `A` and `B`. Therefore, the values of all nodes in the set `P` will remain unchanged. However, for the nodes `U` and `V`, their value will be replaced with the XOR value with `k`.\n\nSo, for any two non-adjacent nodes `U` and `V` in the tree we can replace their values with the XOR values as if they were connected by an edge. Let\'s call this operation as "effective operation" for simplicity.\n\nAfter performing a sequence of effective operations on some pairs of nodes, exactly `m` nodes in the tree have their value replaced with the XOR value (where `m <= n` and `n` denotes the number of nodes in the tree). It can be observed that the value of `m` will always be `even` because "effective operation" is performed on a pair of nodes.\n\nNow, the brute force approach is based on recursion. During recursion, it\'s crucial to incorporate both: the node\'s value with XOR operation (XORing with `k`) and without XOR operation while traversing the tree. We try to maximize the total sum of the values, where the operation is performed on an **even** number of nodes.\n\nLet\'s adapt our recursive solution based on these insights:\n\n- The base case occurs when we have traversed through all the nodes of the tree. If the number of nodes on which we have performed the operation is even, we return 0. Otherwise, we return `INT_MIN` (minimum integer value).\n    \n- We also need to include the parity of the number of elements on which the operation has been performed as a parameter in the recursive solution. If the number of operated elements is even, it is a valid assignment.\n    \n\n> Parity of a number refers to whether it contains an odd or even number of 1-bits.\n\n- The two choices that we have here for every node are to perform an operation on it or not. The recursive calls for each case can be explained as:\n    \n    - If we perform the operation on the node at the position `index`, then the value of this node would be modified to `nums[index] XOR k`. Since we are operating on a node, the parity of the total number of elements on which the XOR operation has been performed will be flipped. Therefore, even parity flips to odd, and vice versa. To obtain the answer for this case, we will store the sum of `nums[index] XOR k` and the subsequent recursive function call for the next node at `index+1` and the flipped parity (denoted by `isEven XOR 1`).\n        \n    - If we do not perform the operation on the node at the position `index`, then the value of this node would remain the same. The parity of the total number of elements on which the operation is performed will remain the same. To obtain the answer for this case, we will store the sum of `nums[index]` and the subsequent recursive function call for the next node at `index+1` and the given parity.\n        \n- Since we want to maximize the sum of all nodes, we will return the maximum value of both the cases discussed above.\n    \n\nThe recursive approach will result in Time Limit Exceeded (TLE) issues due to the exponential nature of possibilities.\n\nTo tackle this issue, we\'ll use dynamic programming (DP) with a two-dimensional table.\n\nThe DP table caches the results of subproblems, with rows representing different indices of the nodes given by `index` and columns representing the parity of the number of operated nodes denoted by `isEven`(`0` indicates `odd`, `1` indicates `even` parity). Each cell stores an integer denoting the maximum possible sum of all the nodes up to `index` and where the parity of the number of operated nodes is `isEven`.\n\nBy caching the calculated states in the dp table, we can avoid recalculating the result for the same combination of index and parity. When encountering a state that has already been computed and stored in the dp table, instead of recursively exploring further, we can directly retrieve the cached result, significantly reducing the time complexity of the algorithm.\n\n#### Algorithm\n\n##### Main Function: `maximumValueSum(nums, k, edges)`\n\n1. Initialize a 2D memoization array `memo` with all values set to `-1`.\n2. Call the helper function `maxSumOfNodes` with the initial parameters:\n    - `index = 0`\n    - `isEven = 1` (start with an odd number of elements)\n    - `nums = the input array`\n    - `k = the given XOR value`\n    - `memo = the initialized memoization array`\n3. Return the result from the `maxSumOfNodes` function.\n\n##### Recursive Function: `maxSumOfNodes(index, isEven, nums, k, memo)`\n\n1. If the `index` is equal to the size of the `nums` array, return:\n    - If `isEven` is 1, return 0 (no operation performed on an odd number of elements).\n    - Else, return `INT_MIN`.\n2. If the result for the current `index` and `isEven` is already memoized, return the memoized value.\n3. Calculate the maximum sum of nodes in two cases:\n    - `noXorDone`: No XOR operation is performed on the current element.\n        - The sum is the current element value `nums[index]` plus the maximum sum of the remaining elements.\n    - `xorDone`: The XOR operation is performed on the current element.\n        - The sum is the current element value `nums[index] ^ k` plus the maximum sum of the remaining elements with `isEven` flipped.\n4. Memoize the maximum of `noXorDone` and `xorDone`, and return the result.\n\n#### Implementation\n```java []\nclass Solution {\n\n        public long maximumValueSum(int[] nums, int k, int[][] edges) {\n            long[][] memo = new long[nums.length][2];\n            for (long[] row : memo) {\n                Arrays.fill(row, -1);\n            }\n            return maxSumOfNodes(0, 1, nums, k, memo);\n        }\n\n        private long maxSumOfNodes(int index, int isEven, int[] nums, int k,\n                long[][] memo) {\n            if (index == nums.length) {\n                // If the operation is performed on an odd number of elements return\n                // INT_MIN\n                return isEven == 1 ? 0 : Integer.MIN_VALUE;\n            }\n            if (memo[index][isEven] != -1) {\n                return memo[index][isEven];\n            }\n            // No operation performed on the element\n            long noXorDone = nums[index] + maxSumOfNodes(index + 1, isEven, nums, k, memo);\n            // XOR operation is performed on the element\n            long xorDone = (nums[index] ^ k) +\n                    maxSumOfNodes(index + 1, isEven ^ 1, nums, k, memo);\n\n            // Memoize and return the result\n            return memo[index][isEven] = Math.max(xorDone, noXorDone);\n        }\n    }\n```\n```python []\nclass Solution:\n    def maxSumOfNodes(self, index, isEven, nums, k, memo):\n        if index == len(nums):\n            # If the operation is performed on an odd number of elements return INT_MIN\n            return 0 if isEven == 1 else -float("inf")\n        if memo[index][isEven] != -1:\n            return memo[index][isEven]\n\n        # No operation performed on the element\n        noXorDone = nums[index] + self.maxSumOfNodes(index + 1, isEven, nums, k, memo)\n        # XOR operation is performed on the element\n        xorDone = (nums[index] ^ k) + self.maxSumOfNodes(\n            index + 1, isEven ^ 1, nums, k, memo\n        )\n\n        # Memoize and return the result\n        memo[index][isEven] = max(xorDone, noXorDone)\n        return memo[index][isEven]\n\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        memo = [[-1] * 2 for _ in range(len(nums))]\n        return self.maxSumOfNodes(0, 1, nums, k, memo)\n```\n```c++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k,\n                              vector<vector<int>>& edges) {\n        vector<vector<long long>> memo(nums.size(), vector<long long>(2, -1));\n        return maxSumOfNodes(0, 1, nums, k, memo);\n    }\n\nprivate:\n    long long maxSumOfNodes(int index, int isEven, vector<int>& nums, int k,\n                            vector<vector<long long>>& memo) {\n        if (index == nums.size()) {\n            // If the operation is performed on an odd number of elements return\n            // INT_MIN\n            return isEven == 1 ? 0 : INT_MIN;\n        }\n        if (memo[index][isEven] != -1) {\n            return memo[index][isEven];\n        }\n        // No operation performed on the element\n        long long noXorDone =\n            nums[index] + maxSumOfNodes(index + 1, isEven, nums, k, memo);\n        // XOR operation is performed on the element\n        long long xorDone = (nums[index] ^ k) +\n                            maxSumOfNodes(index + 1, isEven ^ 1, nums, k, memo);\n\n        // Memoize and return the result\n        return memo[index][isEven] = max(xorDone, noXorDone);\n    }\n};\n```\n\n\n    \n\n#### Complexity Analysis\n\nLet nnn be the number of nodes in the tree.\n\n- Time complexity: $$O(n)$$\n    \n    The time complexity of the `maxSumOfNodes` function can be analyzed by considering the number of unique subproblems that need to be solved. There are at most n\u22C52n \\\\cdot 2n\u22C52 unique subproblems, indexed by `index` and `isEven` values, because the number of possible values for `index` is `n` and `isEven` is `2` (parity).\n    \n    Here, each subproblem is computed only once (due to memoization). So, the time complexity is bounded by the number of unique subproblems.\n    \n    Therefore, the time complexity can be stated as $$O(n)$$.\n    \n- Space complexity: $$O(n)$$\n    \n    The space complexity of the algorithm is primarily determined by two factors: the auxiliary space used for memoization and the recursion stack space. The memoization table, denoted as `memo`, consumes O(n) space due to its size being proportional to the length of the input node list.\n    \n    Additionally, the recursion stack space can grow up to O(n) in the worst case, constrained by the length of the input node list, as each recursive call may add a frame to the stack.\n    \n    Therefore, the overall space complexity is the sum of these two components, resulting in O(n)+O(n) + O(n), which simplifies to $$O(n)$$.\n    \n\n---\n\n### Approach 2: Bottom-up Dynamic Programming (Tabulation)\n\n#### Intuition\n\nTabulation is a dynamic programming technique that involves systematically iterating through all possible combinations of changing parameters. Since tabulation operates iteratively, rather than recursively, it does not require overhead for the recursive stack space, making it more efficient than memoization. We have two variables that change as we progress through the node values: the current index we\'re considering and the parity of even elements. To thoroughly explore the combinations, we use two nested loops to iterate through these variables.\n\nFirst, let\'s establish the base case:\n\n```cpp\nif (index == nums.size()) { \n    return isEven == 1 ? 0 : INT_MIN;\n} \n```\n\nWe represent this base case in our tabulation matrix as `dp[nums.size()][1] = 0` and `dp[nums.size()][0] = INT_MIN`. This indicates that if the parity of the number of operations after iterating the array is odd, then it is an invalid assignment.\n\nOur ultimate goal is to determine the maximum sum of all node values after performing the operation on an even number of nodes, and this information will be stored in `dp[0][1]`. To accomplish this, we traverse through every combination of index and parity using the two nested loops. The outer loop iterates over the index, while the inner loop makes the choice of parity (1 for even and 0 for odd).\n\nThroughout this traversal, we evaluate each state and update our tabulation matrix accordingly. Upon completing the traversal of the entire array, the value of `dp[0][1]` represents the maximum node value sum possible after performing all operations.\n\n#### Algorithm\n\n1. Initialize a 2D dynamic programming array `dp` with dimensions `(n + 1) x 2`, where `n` is the size of the `nums` array.\n2. Initialize the base case values:\n    - `dp[n][1] = 0` (no operation performed on an odd number of elements)\n    - `dp[n][0] = INT_MIN`\n3. Iterate through the `nums` array in reverse order (from `n - 1` to `0`):\n    - For each index `index` and each parity state `isEven` (0 or 1):\n        - Calculate the maximum value sum in two cases:\n            - `performOperation`: Perform the XOR operation on the current element.\n                - The sum is `dp[index + 1][isEven ^ 1] + (nums[index] ^ k)`.\n            - `dontPerformOperation`: Don\'t perform the XOR operation on the current element.\n                - The sum is `dp[index + 1][isEven] + nums[index]`.\n        - Update `dp[index][isEven]` with the maximum of `performOperation` and `dontPerformOperation`.\n4. Return the value stored in `dp[0][1]`, which represents the maximum value sum when starting with an odd number of elements.\n\n#### Implementation\n\n```java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        int n = nums.length;\n        long[][] dp = new long[n + 1][2];\n        dp[n][1] = 0;\n        dp[n][0] = Integer.MIN_VALUE;\n        \n        for (int index = n - 1; index >= 0; index--) {\n            for (int isEven = 0; isEven <= 1; isEven++) {\n                // Case 1: we perform the operation on this element.\n                long performOperation = dp[index + 1][isEven ^ 1] + (nums[index] ^ k);\n                // Case 2: we don\'t perform operation on this element.\n                long dontPerformOperation = dp[index + 1][isEven] + nums[index];\n\n                dp[index][isEven] = Math.max(performOperation, dontPerformOperation);\n            }\n        }\n        \n        return dp[0][1];\n    }\n}\n```\n```python []\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        n = len(nums)\n        dp = [[0] * 2 for _ in range(n + 1)]\n        dp[n][1] = 0\n        dp[n][0] = -float(\'inf\')\n        \n        for index in range(n - 1, -1, -1):\n            for isEven in range(2):\n                # Case 1: we perform an operation on this element.\n                performOperation = dp[index + 1][isEven ^ 1] + (nums[index] ^ k)\n                # Case 2: we don\'t perform operation on this element.\n                dontPerformOperation = dp[index + 1][isEven] + nums[index]\n\n                dp[index][isEven] = max(performOperation, dontPerformOperation)\n        \n        return dp[0][1]\n```\n```c++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k,\n                              vector<vector<int>>& edges) {\n        int n = nums.size();\n        vector<vector<long long>> dp(n + 1, vector<long long>(2, 0));\n        dp[n][1] = 0;\n        dp[n][0] = INT_MIN;\n        \n        for (int index = n - 1; index >= 0; index--) {\n            for (int isEven = 0; isEven <= 1; isEven++) {\n                // Case 1: we perform the operation on this element.\n                long long performOperation =\n                    dp[index + 1][isEven ^ 1] + (nums[index] ^ k);\n                // Case 2: we don\'t perform operation on this element.\n                long long dontPerformOperation =\n                    dp[index + 1][isEven] + nums[index];\n\n                dp[index][isEven] = max(performOperation, dontPerformOperation);\n            }\n        }\n        return dp[0][1];\n    }\n};\n```\n\n#### Complexity Analysis\n\nLet nnn be the number of elements in the node value list.\n\n- Time complexity: $$O(n)$$\n    \n    We iterate through a nested loop where the total number of iterations is given by n\u22C52n \\\\cdot 2n\u22C52. Inside the nested loops, we perform constant time operations. Therefore, time complexity is given by O(n).\n    \n- Space complexity: $$O(n)$$\n    \n    Since we create a new `dp` matrix of size n\u22C52n \\\\cdot 2n\u22C52, the total additional space becomes n\u22C52n \\\\cdot 2n\u22C52. So, the net space complexity is O(n).\n    \n\n---\n\n### Approach 3: Greedy (Sorting based approach)\n\n#### Intuition\n\nIf the operation is performed on a node indexed at `U`, the new value of the node would become `nums[U] XOR k`. For every node, the net change in its value after performing the operation is given by `netChange[U] = nums[U] XOR k - nums[U]`.\n\nIf this net change is greater than zero, it will increase the total sum of all node values. Otherwise, it would decrease it.\n\nLet\'s assume we want to perform the "effective operation" on a pair of nodes that would provide the greatest increment to the node sum. Observe that choosing the nodes with the greatest positive `netChange` values will provide the greatest increment to node sum.\n\nFor all nodes, we can calculate their net change values using the formula discussed above. On sorting these values in **decreasing** order, we can pick the values in pairs from the start of the sorted `netChange` array with a positive sum.\n\nIf the sum of a pair is positive, then it will increase the value of the total node sum when the operation is performed on this pair.\n\n#### Algorithm\n\n1. Initialise the `netChange` array of size `n` and an integer `nodeSum` that stores the current sum of `nums`. Here, `n` is the size of the `nums` array.\n2. Iterate through the `nums` array (from `0` to `n-1`):\n    - For each index, store the value of `netChange` using the idea discussed in intuition.\n3. Sort the array `netChange` in decreasing order.\n4. Iterate through the `netChange` array (from `0` to `n-1`, stepsize = `2`):\n    - If we can not create a pair of adjacent elements, break the iteration.\n    - If the sum of a pair of adjacent elements is positive then add this sum to `nodeSum`.\n5. After iterating through all `netChange` elements, return `nodeSum` as the maximum possible sum of nodes after performing the operations.\n\n\n#### Implementation\n\n```java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        int n = nums.length;\n        int[] netChange = new int[n];\n        long nodeSum = 0;\n\n        for (int i = 0; i < n; i++) {\n            netChange[i] = (nums[i] ^ k) - nums[i];\n            nodeSum += nums[i];\n        }\n\n        Arrays.sort(netChange);\n        // Reverse the sorted array\n        for (int i = 0; i < n / 2; i++) {\n            int temp = netChange[i];\n            netChange[i] = netChange[n - 1 - i];\n            netChange[n - 1 - i] = temp;\n        }\n\n        for (int i = 0; i < n; i += 2) {\n            // If netChange contains odd number of elements break the loop\n            if (i + 1 == n) {\n                break;\n            }\n            long pairSum = netChange[i] + netChange[i + 1];\n            // Include in nodeSum if pairSum is positive\n            if (pairSum > 0) {\n                nodeSum += pairSum;\n            }\n        }\n        return nodeSum;\n    }\n}\n```\n```python []\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        n = len(nums)\n        netChange = [(nums[i] ^ k) - nums[i] for i in range(n)]\n        nodeSum = sum(nums)\n\n        netChange.sort(reverse=True)\n\n        for i in range(0, n, 2):\n            # If netChange contains odd number of elements break the loop\n            if i + 1 == n:\n                break\n            pairSum = netChange[i] + netChange[i + 1]\n            # Include in nodeSum if pairSum is positive\n            if pairSum > 0:\n                nodeSum += pairSum\n\n        return nodeSum\n```\n```c++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k,\n                              vector<vector<int>>& edges) {\n        vector<int> netChange;\n        long long nodeSum = 0;\n        \n        for (int i = 0; i < nums.size(); i++) {\n            netChange.push_back((nums[i] ^ k) - nums[i]);\n            nodeSum += 1ll * nums[i];\n        }\n        \n        // Sort netChange in decreasing order\n        sort(netChange.begin(), netChange.end(), greater<int>());\n        \n        for (int i = 0; i < netChange.size(); i += 2) {\n            // If netChange contains odd number of elements break the loop\n            if (i + 1 == netChange.size()) {\n                break;\n            }\n            long long pairSum = netChange[i] + netChange[i + 1];\n            \n            // Include in nodeSum if pairSum is positive\n            if (pairSum > 0) {\n                nodeSum += pairSum;\n            }\n        }\n        return nodeSum;\n    }\n};\n```\n\n\n\n\n#### Complexity Analysis\n\nLet nnn be the number of elements in the node value list.\n\n- Time complexity:O(n\u22C5logn)\n    \n    Other than the `sort` invocation, we perform simple linear operations on the list, so the runtime is dominated by the O(n\u22C5logn) complexity of sorting.\n    \n- Space complexity: O(n)\n    \n    Since we create a new `netChange` array of size `n` and sort it, the additional space becomes O(n) for `netChange` array and O(logn) or O(n) for sorting it (depending on the sorting algorithm used). So, the net space complexity is O(n).\n    \n\n---\n\n### Approach 4: Greedy (Finding local maxima and minima)\n\n#### Intuition\n\nRecall that "effective operation" allows us to pick any two nodes and perform an operation on it. Let\'s assume for two nodes, the `netChange` values are positive. If we pick both these nodes as a pair to perform "effective operation", the node sum value will be increased. So, we can observe that if the number of elements with positive `netChange` values is even, then all of them can be included in the final sum to maximize it.\n\nIf the number of elements with positive `netChange` values is **odd**, then let\'s assume that `positiveMinimum` denotes the **minimum positive** value and `negativeMaximum` denotes the **maximum non-positive** value in the `netChange` array. It is clear that both these values will occur as a pair in the `netChange` array.\n\nNow, there can be two cases for the same:-\n\n1. If the sum of `positiveMinimum` and `negativeMaximum` is greater than zero, then the node value sum will be increased by including this pair. So, we include both elements.\n    \n2. If the sum of `positiveMinimum` and `negativeMaximum` is less than or equal to zero, then the node value sum will be decreased or have no change on including this pair. So, we exclude this pair.\n    \n\nTherefore, we don\'t need the `netChange` array from the previous approach. We calculate `positiveMinimum` and `negativeMaximum` values which is enough to calculate the maximum node value sum possible for the array.\n\n#### Algorithm\n\n1. Initialize integers `positiveMinimum` and `negativeMaximum` with `INT_MAX` and `INT_MIN` respectively. Also, initialize `count` and `sum` with `0`.\n2. Iterate through the `nums` array (from `0` to `n - 1`):\n    - Add the unchanged node values to `sum`.\n    - Calculate the value of `netChange` for the current node.\n        - If `netChange` is positive, assign the minimum of `netChange` and `positiveMinimum` to `positiveMinimum`. Add `netChange` to the `sum` and increment the `count` by 1.\n        - If `netChange` is non-positive, assign the maximum of `netChange` and `negativeMaximum` to `negativeMaximum`.\n3. If the `count` of number values with positive `netChange` is even, we return the current `sum` as the maximum node value sum possible.\n4. If the `count` is odd, we can either subtract `positiveMinimum` or add `negativeMaximum` to make the `count` even. The maximum of both these cases is returned as the maximum node value sum.\n\n\n\n#### Implementation\n```java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        long sum = 0;\n        int count = 0, positiveMinimum = (1 << 30), negativeMaximum = -1 * (1 << 30);\n\n        for (int nodeValue : nums) {\n            int operatedNodeValue = nodeValue ^ k;\n            sum += nodeValue;\n            int netChange = operatedNodeValue - nodeValue;\n            if (netChange > 0) {\n                positiveMinimum = Math.min(positiveMinimum, netChange);\n                sum += netChange;\n                count++;\n            } else {\n                negativeMaximum = Math.max(negativeMaximum, netChange);\n            }\n        }\n\n        // If the number of positive netChange values is even, return the sum.\n        if (count % 2 == 0) {\n            return sum;\n        }\n\n        // Otherwise return the maximum of both discussed cases.\n        return Math.max(sum - positiveMinimum, sum + negativeMaximum);\n    }\n}\n```\n```python []\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        sumVal = 0\n        count = 0\n        positiveMinimum = 1 << 30\n        negativeMaximum = -1 * (1 << 30)\n\n        for nodeValue in nums:\n            operatedNodeValue = nodeValue ^ k\n            sumVal += nodeValue\n            netChange = operatedNodeValue - nodeValue\n            if netChange > 0:\n                positiveMinimum = min(positiveMinimum, netChange)\n                sumVal += netChange\n                count += 1\n            else:\n                negativeMaximum = max(negativeMaximum, netChange)\n\n        # If the number of positive netChange values is even, return the sum.\n        if count % 2 == 0:\n            return sumVal\n\n        # Otherwise return the maximum of both discussed cases.\n        return max(sumVal - positiveMinimum, sumVal + negativeMaximum)\n```\n```c++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k,\n                              vector<vector<int>>& edges) {\n        long long sum = 0;\n        int count = 0, positiveMinimum = (1 << 30),\n            negativeMaximum = -1 * (1 << 30);\n            \n        for (int nodeValue : nums) {\n            int operatedNodeValue = nodeValue ^ k;\n            sum += nodeValue;\n            int netChange = operatedNodeValue - nodeValue;\n            \n            if (netChange > 0) {\n                positiveMinimum = min(positiveMinimum, netChange);\n                sum += netChange;\n                count++;\n            } else {\n                negativeMaximum = max(negativeMaximum, netChange);\n            }\n        }\n        \n        // If the number of positive netChange values is even return the sum.\n        if (count % 2 == 0) {\n            return sum;\n        }\n        \n        // Otherwise return the maximum of both discussed cases.\n        return max(sum - positiveMinimum, sum + negativeMaximum);\n    }\n};\n```\n\n```\n\n```\n\n#### Complexity Analysis\n\nLet nnn be the number of elements in the node value list.\n\n- Time complexity: O(n)\n    \n    We perform a single pass linear scan on the list which takes O(n) time. All other operations are performed in constant time. This makes the net time complexity as O(n).\n    \n- Space complexity: O(1)\n    \n    We do not allocate any additional auxiliary memory proportional to the size of the given node list. Therefore, overall space complexity is given by O(1).\n\n\n# Code\n```\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        long sum = 0;\n        int count = 0, positiveMinimum = (1 << 30), negativeMaximum = -1 * (1 << 30);\n\n        for (int nodeValue : nums) {\n            int operatedNodeValue = nodeValue ^ k;\n            sum += nodeValue;\n            int netChange = operatedNodeValue - nodeValue;\n            if (netChange > 0) {\n                positiveMinimum = Math.min(positiveMinimum, netChange);\n                sum += netChange;\n                count++;\n            } else {\n                negativeMaximum = Math.max(negativeMaximum, netChange);\n            }\n        }\n\n        // If the number of positive netChange values is even, return the sum.\n        if (count % 2 == 0) {\n            return sum;\n        }\n\n        // Otherwise return the maximum of both discussed cases.\n        return Math.max(sum - positiveMinimum, sum + negativeMaximum);\n    }\n}\n```
['Python', 'C++', 'Java', 'Python3']