💯Beats💯Python✅Java✅C++✅Step-By-Step🔥Clean code w/ Explanation⚡️
Step 1: Possibilities For Each Node \uD83D\uDE2E\n\n- Each node can either be nums[i] or nums[i]^k\n- This is because nums[i]^k^k = nums[i] \uD83D\uDCDD\n\n# St
# Step 1: Possibilities For Each Node \uD83D\uDE2E\n\n- Each node can either be ```nums[i]``` or ```nums[i]^k```\n- This is because ```nums[i]^k^k = nums[i]``` \uD83D\uDCDD\n\n# Step 2: Removing The Tree \uD83C\uDF32\n\n- By definition of a tree, there exists a path \uD83C\uDFDE between any 2 nodes\n- If we apply the operation on every edge on a path between 2 nodes, only the start and end nodes will be changed \uD83D\uDD00 (Write some examples)\n- This means that we can take any 2 nodes ```nums[i]``` and ```nums[j]``` and set them both to ```nums[i]^k``` and ```nums[j]^k```, regardless of the edges \u274C\n\n# Step 3: Picking pairs \u26CF\uFE0F\n\n- If we can xor any 2 nodes by ```k``` multiple times, we can xor any even number of nodes by ```k``` \uD83E\uDD14\n- Lets try to pick every node where ```nums[i]^k > nums[i]```, meaning that our sum increases by picking that node \uD83E\uDDE0\n- If there are an even number of nodes like that, we just pick all of them \uD83E\uDD2F\n- Otherwise, we have to choose between not picking a node that we have picked, or picking another node\n\n# Step 4: Code explanation\n\n- Let ```sum``` be the sum of all ```nums[i]``` \u2795\n- Let ```add[i]``` be ```nums[i]^k - nums[i]```\n- If ```add[i]``` is positive, ```nums[i]^k > nums[i]```\n- Let ```sum``` be our baseline answer, and lets try to take as many positive ```add[i]``` as we can\n- Let\'s also keep track of the minimum positive number in ```add```, and the maximum negative number \u261D\uFE0F\n- These numbers are useful when we are deciding whether to remove a node or add the node if the number of nodes we pick is odd\n\n# Complexity\n- Time complexity: $$O(n)$$\u26A1\uFE0F\u26A1\uFE0F\n- Space complexity: $$O(n)$$\u26A1\uFE0F\u26A1\uFE0F\n\n# \uD83E\uDDD1\u200D\uD83D\uDCBB\uFE0F\n``` Python []\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        sum = 0\n        add = [0]*len(nums)\n        for i in range(len(nums)):\n            sum+=nums[i]\n            xor = nums[i]^k\n            add[i] = xor-nums[i]\n        minPos = 1e20\n        maxNeg = -1e20\n        posCount = 0\n        posSum = 0\n        for i in add:\n            if i>0:\n                minPos = min(minPos,i)\n                posSum+=i\n                posCount+=1\n            else:\n                maxNeg = max(maxNeg,i)\n        if posCount%2 == 0:\n            return posSum+sum\n        else:\n            removePos = posSum-minPos+sum\n            addNeg = posSum+maxNeg+sum\n            return max(removePos,addNeg)\n```\n``` C++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        long long sum = 0;\n        vector<int> add(nums.size());\n        for(int i = 0; i<nums.size(); i++){\n            sum+=nums[i];\n            int xorVal = nums[i]^k;\n            add[i] = xorVal-nums[i];\n        }\n        int minPos = INT_MAX, maxNeg = INT_MIN;\n        int posCount = 0;\n        long long posSum = 0;\n        for(int i: add){\n            if(i>0){\n                minPos = min(minPos,i);\n                posSum+=i;\n                posCount++;\n            }else{\n                maxNeg = max(maxNeg,i);\n            }\n        }\n        if(posCount%2 == 0){\n            return posSum+sum;\n        }else{\n            long long removePos = posSum-minPos+sum;\n            long long addNeg = posSum+maxNeg+sum;\n            return max(removePos,addNeg);\n        }\n    }\n};\n```\n``` Java []\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        long sum = 0;\n        int[] add = new int[nums.length];\n        for(int i = 0; i<nums.length; i++){\n            sum+=nums[i];\n            int xor = nums[i]^k;\n            add[i] = xor-nums[i];\n        }\n        int minPos = Integer.MAX_VALUE, maxNeg = Integer.MIN_VALUE;\n        int posCount = 0;\n        long posSum = 0;\n        for(int i: add){\n            if(i>0){\n                minPos = Math.min(minPos,i);\n                posSum+=i;\n                posCount++;\n            }else{\n                maxNeg = Math.max(maxNeg,i);\n            }\n        }\n        if(posCount%2 == 0){\n            return posSum+sum;\n        }else{\n            long removePos = posSum-minPos+sum;\n            long addNeg = posSum+maxNeg+sum;\n            return Math.max(removePos,addNeg);\n        }\n    }\n}\n```
['Bit Manipulation', 'C++', 'Java', 'Python3']