Ignore edge Greedy approach with explanation | clean code | [c++/java/python/go]
Intuition\n- This solution is based on we can xor operation on any pair of nodes irrespective of any direct edge between them. How??\n    - For a parent node we
# Intuition\n- This solution is based on we can xor operation on any pair of nodes irrespective of any direct edge between them. How??\n    - **For a parent node we can xor of it with any of its direct child or indirect child node.**\n    - Suppose we have a parent node a with direct child b which has child c like  a--->b--->c. Now we can take xor for edge b->c as mentioned in problem statement. We can again take xor on a->b.\n    - Since we did xor twice on b so its value wont change effectively we did xor between a & c. hence proving our first statement.\n    - **We can take xor between two nodes present in left and right subtree.**\n    - For two nodes a, b having common parent c. We can take xor of a^c then b^c since we did xor twice on c its value wont change so effectively its xor on a&b proving our original statement.\n- Now we can greedily pick pairs whose xored value will give us maximum sum result.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n- Create a difference array which stores difference in values if we take original value vs xored value\n- sort this on descending order and pick pairs such that net sum is positive\n- Add this with net sum of all initial nodes and we get our result.\n- We can also use discard approach where we keep track of mim difference and discard it to make pairs\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(nlogn) for sorting difference array. We can make it O(n) if we use discard approach\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) for storing diff array. We can make it constant space if we use discard based approach\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```c++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nodes, int k, vector<vector<int>>& e) {\n        int n = nodes.size();\n        vector<int> diff(n, 0);\n        long long sum = 0l;\n        for(int i=0;i<n;i++) {\n            diff[i] = (nodes[i]^k )- nodes[i];\n            sum+=nodes[i]*1l;\n        } \n        sort(diff.begin(), diff.end(), greater<int>());\n        for(int i=0;i<n-1;i+=2) {\n            if((diff[i] + diff[i+1])>0) {\n                sum+=(diff[i] + diff[i+1])*1l;\n            }\n        }\n        return sum;\n    }\n};\n```\n```python []\nclass Solution(object):\n    def maximumValueSum(self, nums, k, edges):\n        n = len(nums)\n        diff = [0] * n\n        total_sum = 0\n\n        for i in range(n):\n            diff[i] = (nums[i] ^ k) - nums[i]\n            total_sum += nums[i]\n\n        diff.sort(reverse=True)\n\n        for i in range(0, n-1, 2):\n            if diff[i] + diff[i+1] > 0:\n                total_sum += diff[i] + diff[i+1]\n\n        return total_sum\n\n```\n```go []\n\nfunc maximumValueSum(nodes []int, k int, e [][]int) int64 {\n\tn := len(nodes)\n\tdiff := make([]int, n)\n\tvar sum int64\n\n\tfor i := 0; i < n; i++ {\n\t\tdiff[i] = (nodes[i] ^ k) - nodes[i]\n\t\tsum += int64(nodes[i])\n\t}\n\n\tsort.Slice(diff, func(i, j int) bool {\n\t\treturn diff[i] > diff[j]\n\t})\n\n\tfor i := 0; i < n-1; i += 2 {\n\t\tif diff[i]+diff[i+1] > 0 {\n\t\t\tsum += int64(diff[i] + diff[i+1])\n\t\t}\n\t}\n\n\treturn sum\n}\n```\n``` Java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        int n = nums.length;\n        int[] diff = new int[n];\n        long totalSum = 0;\n\n        for (int i = 0; i < n; i++) {\n            diff[i] = (nums[i] ^ k) - nums[i];\n            totalSum += nums[i];\n        }\n\n        Arrays.sort(diff);\n        \n        for (int i = n - 1; i > 0; i -= 2) {\n            if ((diff[i] + diff[i - 1]) > 0) {\n                totalSum += (diff[i] + diff[i - 1]);\n            }\n        }\n\n        return totalSum;\n    }\n}\n\n```\n
['C++']