🔥 Go Beat 100% || O(n) / O(1) || With explanation 🔥
Intuition\n1. XORing a number twice with k leaves it unchanged.\uFF08a XOR k XOR k = a\uFF09\n2. For a path from node a to node b in a tree, if each edge on the
# Intuition\n1. XORing a number twice with `k` leaves it unchanged.\uFF08a XOR k XOR k = a\uFF09\n2. For a path from node `a` to node `b` in a tree, if each edge on the path is XORed, then all nodes on the path except `a` and `b` undergo an even number of XOR operations, keeping their values unchanged. Hence, the problem is equivalent to XORing `k` simultaneously to any two nodes, eliminating the need for constructing a tree.\n3. There are always an even number of elements XORed with k.\nTherefore, the problem transforms into: select an even number of elements from nums to XOR with k, maximizing the sum of all elements in nums.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDefine `f[i][0]`  as the maximum sum of elements obtained by XORing `k` with an even number of elements chosen from the first `i` numbers in `nums`, while `f[i][1]`  as the maximum sum of elements obtained by XORing `k` with an odd number of elements chosen from the first `i` numbers in `nums`.\nTherefore, we have the following transition equations: \n$$f[i][0] = \\max(f[i-1][0]+nums[i-1], f[i-1][1] + nums[i-1] \u2295 k) $$\n$$f[i][1] = \\max(f[i-1][0]+nums[i-1], f[i-1][0] + nums[i-1] \u2295 k) $$\nAlso we can optimize the space complexity from $O(n)$ to $O(1)$ by using only two variables to store the maximum sum of elements.\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```\nfunc maximumValueSum(nums []int, k int, edges [][]int) int64 {\n\tf0, f1 := 0, math.MinInt\n\tfor _, num := range nums {\n\t\tf0, f1 = max(f0+num, f1+(num^k)), max(f1+num, f0+(num^k))\n\t}\n\treturn int64(f0)\n}\n```
['Dynamic Programming', 'Go']