✅Detailed Explanation🔥2 Approaches🔥🔥Extremely Simple and effective🔥🔥🔥
\uD83C\uDFAFProblem Explanation:\nYou are given an undirected tree with n nodes numbered from 0 to n - 1 where each node has some value (see nums) and array nod
# \uD83C\uDFAFProblem Explanation:\nYou are given an undirected tree with ```n``` nodes numbered from **0 to n - 1** where each node has some value (see ```nums```) and array ```nodes``` which represents edges beetwen nodes. You can perform XOR operation with number ```k``` any number of times on any two nodes which have edge between them in ```edges```. After perfoming them you want to achieve and return maximum possible sum of the tree.\n\n# \uD83D\uDCE5Input:\n- Integer array ```nums``` which represents values for every node.\n- Array ```edges``` which contain list with two values - ```node from``` and ```node to``` (In fact, just forget about this parameter, it\'s just confusing and useless)\n- Integer ```k``` - number with which you will perform XOR operation on connected nodes.\n\n# \uD83D\uDCE4Output:\nThe maximum possible sum of all nodes after perfoming any number of operations.\n\n# \uD83E\uDD14 Intuition\n- The main point in this question is specific of XOR operation. **SO first of all, if you don\'t know what XOR means read this explanation**:\n    - *The XOR (exclusive OR) (frequently indicated as "^") 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 **1010 ^ 1100 = 0110** indicating that the second and third bits differ while the first and fourth bits are the same.*\n- Now you know about XOR let\'s talk a little about its feature. Let\'s get number from explanation **0110** and then perform on it XOR with **1100**, we will get **0110 ^ 1100 = 1010** -> something familiar, isn\'t it? If you look closer you can see that this is the first operand from example from the explanation. Do you know what it means? That means that for two number **a** and **b** will be true that ```(a ^ b) ^ b = a```. **This is one of main point for the solutions so I strongly recommend you to reread this if you haven\'t understanded, consider your own examples or ask questions in comment secion.**\n- Another very important point that, considering last point, you can choose not just any conected nodes to perform XOR but any two from the tree because in the tree you always have a path from one node to another (this is why array ```edges``` is useless). Of course I need to explain this. Imagine you have 3 nodes 0, 1, 2 and edges (0, 1) and (0, 2) (the same tree as in the  description section) and look on picture.\n![image.png](https://assets.leetcode.com/users/images/b308c0c2-5e52-46d0-afa9-0548373e93d7_1716096338.847658.png)\n\n- So, we are managed to XOR two nodes which haven\'t edge beetwen them, in such way I can XOR some node after the second node and so on. Considering that in the tree all nodes have some path between them we can XOR any pair of nodes we want. Now, let\'s move on to the approaches which based on this observations.\n\n\n# \uD83E\uDDE0 Approach 1: Recursion with memoization\nFirst of all - don\'t give up if you don\'t understand this approach. It\'s quite hard to come up with or understand so just move on to the next approach if you don\'t like this.\n- We will do something like Fibonacci numbers - we will go from top to the bottom, calculating all possible states of the problem using recursion and memoization\n- We want to apply this steps to write code for recursion solution:\n    - Initialize memoization array ```temp```\n    - We want to choose "root" of our tree so we can be sure that we traverse it all so let\'s just start with 0. In recursion we want to know on which node we currently are and parity of number of nodes we have XORed all the way to this node.\n    - If we\'ve gone through last node and now we are on the non-existing node then we want to return ```-inf``` if number of nodes we XORed is odd (because we can XOR only pair of them) or 0 if it\'s even (non-existing node mustn\'t affect the sum).\n    - If we already encountered this state then return its maximum result from ```temp```.\n    - Call recursion for both occasions - we are XORing this node and we aren\'t.\n    - Find maximum from two values, write it to the memoization array and return it.\n- Just return result from our recursion function using node 0 as root and is_even to true (we have XORed 0 nodes which is even)\n\n# \uD83D\uDCD2 Complexity\n- \u23F0 Time complexity: O(n), there can be at most 2 * n subproblems (check the size for ```temp``` array)\n- \uD83E\uDDFA Space complexity: O(n) we use O(n) for recursion stack and O(2 * n) for memoization so O(3n) in total or just O(n)\n\n# \uD83E\uDDD1\u200D\uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def maximumValueSum(self, nums: list[int], k: int, edges: list[list[int]]) -> int:\n        n: int = len(nums)\n        temp: list[list[int]] = [[-1 for _ in range(2)] for _ in range(n)]  # temp[current_index(node)][is_even]\n\n        def calculate_max(cur_ind, is_even) -> int:  # cur_ind -> cur_index of the tree and is_even represents whether we have already changed (XOR) even or odd number of nodes \n            if cur_ind == n:  # if we go to node which doesn\'t exist\n                return 0 if is_even else -float("inf")\n            if temp[cur_ind][is_even] != -1:  # if we\'ve already encountered this state\n                return temp[cur_ind][is_even]\n\n            # checking all possible variants (no XOR or XOR)\n            no_xor = nums[cur_ind] + calculate_max(cur_ind + 1, is_even)  # we don\'t change the number of XOR nodes\n            with_xor = (nums[cur_ind] ^ k) + calculate_max(cur_ind + 1, not is_even)  # we added 1 XORed node\n\n            mx_possible = max(no_xor, with_xor)\n            temp[cur_ind][is_even] = mx_possible\n            return mx_possible\n\n        return calculate_max(0, 1)  # is_even == 1 because we have XORed 0 nodes which is even\n```\n``` C++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        int n = nums.size();\n        vector<vector<long long>> temp(n, vector<long long>(2, -1)); // temp[current_index(node)][is_even]\n        \n        return calculateMax(nums, n, k, 0, 1, temp);\n    }\n\nprivate:\n    // calculate_max -> cur_ind -> cur_index of the tree and is_even represents whether we have already changed (XOR) even or odd number of nodes \n    long long calculateMax(vector<int>& nums, int n, int k, int curInd, int isEven, vector<vector<long long>>& temp) {\n        if (curInd == n) {  // if we go to node which doesn\'t exist\n            return isEven == 1 ? 0 : LLONG_MIN;\n        }\n        if (temp[curInd][isEven] != -1) {  // if we\'ve already encountered this state\n            return temp[curInd][isEven];\n        }\n\n        // checking all possible variants (no XOR or XOR)\n        long long noXor = nums[curInd] + calculateMax(nums, n, k, curInd + 1, isEven, temp);  // we don\'t change the number of XOR nodes\n        long long withXor = (nums[curInd] ^ k) + calculateMax(nums, n, k, curInd + 1, !isEven, temp);  // we added 1 XORed node\n\n        long long mxPossible = max(noXor, withXor);\n        temp[curInd][isEven] = mxPossible;\n        return mxPossible;\n    }\n};\n```\n``` JavaScript []\nvar maximumValueSum = function(nums, k, edges) {\n    const n = nums.length;\n    const temp = Array.from({ length: n }, () => [-1, -1]);\n\n    // calculate_max -> cur_ind -> cur_index of the tree and is_even represents whether we have already changed (XOR) even or odd number of nodes \n    function calculateMax(curInd, isEven) {\n        if (curInd === n) {  // if we go to node which doesn\'t exist\n            return isEven === 1 ? 0 : -Infinity;\n        }\n        if (temp[curInd][isEven] !== -1) {  // if we\'ve already encountered this state\n            return temp[curInd][isEven];\n        }\n\n        // checking all possible variants (no XOR or XOR)\n        const noXor = nums[curInd] + calculateMax(curInd + 1, isEven);  // we don\'t change the number of XOR nodes\n        const withXor = (nums[curInd] ^ k) + calculateMax(curInd + 1, 1 - isEven);  // we added 1 XORed node\n\n        const mxPossible = Math.max(noXor, withXor);\n        temp[curInd][isEven] = mxPossible;\n        return mxPossible;\n    }\n\n    return calculateMax(0, 1);  // is_even == 1 because we have XORed 0 nodes which is even\n};\n```\n``` Java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        int n = nums.length;\n        long[][] temp = new long[n][2]; // temp[current_index(node)][is_even]\n        for (int i = 0; i < n; i++) {\n            temp[i][0] = -1;\n            temp[i][1] = -1;\n        }\n\n        return calculateMax(nums, n, k, 0, 1, temp);  // is_even == 1 because we have XORed 0 nodes which is even\n    }\n\n    // calculate_max -> cur_ind -> cur_index of the tree and is_even represents whether we have already changed (XOR) even or odd number of nodes \n    private long calculateMax(int[] nums, int n, int k, int curInd, int isEven, long[][] temp) {\n        if (curInd == n) {  // if we go to node which doesn\'t exist\n            return isEven == 1 ? 0 : Long.MIN_VALUE;\n        }\n        if (temp[curInd][isEven] != -1) {  // if we\'ve already encountered this state\n            return temp[curInd][isEven];\n        }\n\n        // checking all possible variants (no XOR or XOR)\n        long noXor = nums[curInd] + calculateMax(nums, n, k, curInd + 1, isEven, temp);  // we don\'t change the number of XOR nodes\n        long withXor = (nums[curInd] ^ k) + calculateMax(nums, n, k, curInd + 1, 1 - isEven, temp);  // we added 1 XORed node\n\n        long mxPossible = Math.max(noXor, withXor);\n        temp[curInd][isEven] = mxPossible;\n        return mxPossible;\n    }\n}\n```\n``` C []\nlong long calculateMax(int* nums, int n, int k, int curInd, int isEven, long long** temp) {\n    if (curInd == n) {  // if we go to a node that doesn\'t exist\n        return isEven == 1 ? 0 : LLONG_MIN;\n    }\n    if (temp[curInd][isEven] != -1) {  // if we\'ve already encountered this state\n        return temp[curInd][isEven];\n    }\n\n    // checking all possible variants (no XOR or XOR)\n    long long noXor = nums[curInd] + calculateMax(nums, n, k, curInd + 1, isEven, temp);  // we don\'t change the number of XOR nodes\n    long long withXor = (nums[curInd] ^ k) + calculateMax(nums, n, k, curInd + 1, !isEven, temp);  // we added 1 XORed node\n\n    long long mxPossible = noXor > withXor ? noXor : withXor;\n    temp[curInd][isEven] = mxPossible;\n    return mxPossible;\n}\n\nlong long maximumValueSum(int* nums, int numsSize, int k, int** edges, int edgesSize, int* edgesColSize) {\n    int n = numsSize;\n    long long** temp = (long long**)malloc(n * sizeof(long long*)); // temp[current_index(node)][is_even]\n    for (int i = 0; i < n; i++) {\n        temp[i] = (long long*)malloc(2 * sizeof(long long));\n        temp[i][0] = -1;\n        temp[i][1] = -1;\n    }\n\n    long long result = calculateMax(nums, n, k, 0, 1, temp);  // is_even == 1 because we have XORed 0 nodes which is even\n\n    for (int i = 0; i < n; i++) {\n        free(temp[i]);\n    }\n    free(temp);\n\n    return result;\n}\n```\n\n\n# \uD83E\uDDE0 Approach 2: Calculating deltas and sorting\nThis approach is quite easier both to write and understand but have worse time complexity.\n- For every number we want to XOR it with ```k``` and check how we\'ll benefit from this, obviously we always want to increase our sum.\n- Sort the array ```deltas``` which contain XORed values (as we can XOR any pair of nodes as described above we will first XOR those, which will give us better change in sum)\n- Now we want to go through this array by pairs of elements and perform this logic:\n    - If sum of this pair is > 0 then our sum will increase after XORing this two elements, we do so and add this sum to res.\n    - If sum is < 0 then this pair and all pairs after will decrease our sum so we will just go out of loop \n- Return maximum result we have reached\n\n# \uD83D\uDCD2 Complexity\n- \u23F0 Time complexity: O(n logn), we use sorting which is use nlogn time in most languages\n- \uD83E\uDDFA Space complexity: O(n) since we creating array ```deltas``` of size n\n\n# \uD83E\uDDD1\u200D\uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def maximumValueSum(self, nums: list[int], k: int, edges: list[list[int]]) -> int:\n        n: int = len(nums)\n        deltas: list[int] = [(nums[i] ^ k) - nums[i] for i in range(n)]  # represents how will change number after XOR\n        deltas.sort(reverse=True)\n        res: int = sum(nums)\n\n        for start_ind in range(0, n - 1, 2):\n            changing_delta: int = deltas[start_ind] + deltas[start_ind + 1]  # showing whether if would be beneficial if we XOR this two nodes \n            if changing_delta > 0:\n                res += changing_delta\n            else:\n                break\n\n        return res\n```\n``` Java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        int n = nums.length;\n        long[] deltas = new long[n]; // represents how will change number after XOR\n        for (int i = 0; i < n; i++) {\n            deltas[i] = (nums[i] ^ k) - nums[i];\n        }\n        Arrays.sort(deltas);\n        for (int i = 0; i < n / 2; i++) {\n            long temp = deltas[i];\n            deltas[i] = deltas[n - i - 1];\n            deltas[n - i - 1] = temp;\n        }\n\n        long res = 0;\n        for (int num : nums) {\n            res += num;\n        }\n\n        for (int startInd = 0; startInd < n - 1; startInd += 2) {\n            long changingDelta = deltas[startInd] + deltas[startInd + 1]; // showing whether if would be beneficial if we XOR this two nodes \n            if (changingDelta > 0) {\n                res += changingDelta;\n            } else {\n                break;\n            }\n        }\n\n        return res;\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        int n = nums.size();\n        vector<long long> deltas(n); // represents how will change number after XOR\n        for (int i = 0; i < n; i++) {\n            deltas[i] = (nums[i] ^ k) - nums[i];\n        }\n        sort(deltas.rbegin(), deltas.rend());\n\n        long long res = 0;\n        for (int num : nums) {\n            res += num;\n        }\n\n        for (int startInd = 0; startInd < n - 1; startInd += 2) {\n            long long changingDelta = deltas[startInd] + deltas[startInd + 1]; // showing whether if would be beneficial if we XOR this two nodes \n            if (changingDelta > 0) {\n                res += changingDelta;\n            } else {\n                break;\n            }\n        }\n\n        return res;\n    }\n};\n```\n``` JavaScript []\nvar maximumValueSum = function(nums, k, edges) {\n    let n = nums.length;\n    let deltas = new Array(n).fill(0).map((_, i) => (nums[i] ^ k) - nums[i]); // represents how will change number after XOR\n    deltas.sort((a, b) => b - a);\n\n    let res = nums.reduce((acc, num) => acc + num, 0);\n\n    for (let startInd = 0; startInd < n - 1; startInd += 2) {\n        let changingDelta = deltas[startInd] + deltas[startInd + 1]; // showing whether if would be beneficial if we XOR this two nodes \n        if (changingDelta > 0) {\n            res += changingDelta;\n        } else {\n            break;\n        }\n    }\n\n    return res;\n};\n```\n``` C []\n// Comparator function for qsort to sort in descending order\nint cmpfunc(const void *a, const void *b) {\n    return (*(long long *)b - *(long long *)a);\n}\n\nlong long maximumValueSum(int* nums, int numsSize, int k, int** edges, int edgesSize, int* edgesColSize) {\n    int n = numsSize;\n    long long* deltas = (long long*)malloc(n * sizeof(long long)); // represents how will change number after XOR\n\n    for (int i = 0; i < n; i++) {\n        deltas[i] = (nums[i] ^ k) - nums[i];\n    }\n    qsort(deltas, n, sizeof(long long), cmpfunc);\n\n    long long res = 0;\n    for (int i = 0; i < n; i++) {\n        res += nums[i];\n    }\n\n    for (int startInd = 0; startInd < n - 1; startInd += 2) {\n        long long changingDelta = deltas[startInd] + deltas[startInd + 1]; // showing whether if would be beneficial if we XOR this two nodes \n        if (changingDelta > 0) {\n            res += changingDelta;\n        } else {\n            break;\n        }\n    }\n\n    free(deltas);\n    return res;\n}\n```\n\n## \uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning! \uD83D\uDCDA\n\n### Please consider *upvote* because I try really hard not just to put here my code and rewrite testcase to show that it works but explain you WHY it works and HOW. Thank you\u2764\uFE0F\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/5fbeecf2-18f6-4dce-a4a0-f11c859e46ad_1714711173.2665718.png)\n
['Dynamic Programming', 'Greedy', 'Bit Manipulation', 'Tree', 'C', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']