Java O(n) time and O(1) extra memory DP simple solution
Intuition\nNote that you can actually pick any two nodes and apply the xor operation on them. \n\nYou can do this by applying the given operation consecutively 
# Intuition\nNote that **you can actually pick any two nodes and apply the xor operation on them**. \n\nYou can do this by applying the given operation consecutively on the chosen nodes and their parents, and then their parents and their parents\' parents and so on until the lowest common ancestor (lca), which would leave the value of the lca unchanged, as `num xor k xor k == num` holds for any numbers num and k.\n\n# Approach\nWe can now reduce this problem to the following problem:\n\n\n>Given two arrays, `options1` and `options2`, both of size n, where **options1[i] = nums[i]** and **options2[i] = nums[i] xor k**, choose an **even** amount of elements from the second array, such that the sum of those elements and the sum of the remaining elements from the first array (the ones with different indices than the selected numbers in the second array) is **maximized**.\n\nWe can solve this with dynamic programming, where at each step we keep track of the best sum if we have an odd amount of numbers from the second array and the best sum if we have an even amount of numbers from the second array.\n\nThe recursions are\n> bestSumOdd<sub>i</sub> = max(bestSumOdd<sub>i - 1</sub> + options1[i], bestSumEven<sub>i - 1</sub> + options2[i])\n> bestSumEven<sub>i</sub> = max(bestSumEven<sub>i - 1</sub> + options1[i], bestSumOdd<sub>i - 1</sub> + options2[i])\n\n> by choosing at step i an element from options1 we do not add an extra element from the second array (so if we had an odd amount of elements from the second array before, we still do at this step)\n\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$ in the code, but could easily be reduced to $$O(1)$$ extra memory by generating options1[i] and options2[i] when needed. \n\n# Code\n```\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        int n = nums.length;\n\n        if (n == 1) {\n            return nums[0];\n        }\n        \n        int[] options1 = new int[n];\n        int[] options2 = new int[n];\n        \n        for (int i = 0; i < n; i++) {\n            options1[i] = nums[i];\n            options2[i] = nums[i] ^ k;\n        }\n        \n        long bestOdd = options2[0];\n        long bestEven = options1[0];\n        \n        for (int i = 1; i < n; i++) {\n            long newOdd = Math.max(bestOdd + options1[i], \n                                   bestEven + options2[i]);\n            long newEven = Math.max(bestEven + options1[i], \n                                    bestOdd + options2[i]);\n            \n            bestOdd = newOdd;\n            bestEven = newEven;\n        }\n        \n        return bestEven;\n    }\n}\n```
['Java']