🔥 All 4 DP Solutions 🔥 Easiest Hard Problem
Intuition\nAny node say A can be paired with any other node say B by pairing all the nodes from A to B path resulting in double xor of in between elements which
# Intuition\nAny node say A can be paired with any other node say B by pairing all the nodes from A to B path resulting in double xor of in between elements which doesn\'t change it, So the edges are useless here\n\n# Approach\nWe just need to keep sure that the nodes that are changed are even, as they were paired \nThat\'s it, now its a simple DP problem with just a node and a (even counter or flag) states\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity:$$O(n)$$ to $$O(1)$$\n\n# Code\n# Memoization\n```\nclass Solution {\nprivate:\n    long long dp[20001][2];\n    long long f(int idx,int even,vector<int> &nums,int k) {\n        // base cases\n        if(idx >= nums.size()) return even? 0 : -1e9;\n        if(dp[idx][even] != -1) return dp[idx][even];\n\n        long long take = (nums[idx]^k) + f(idx+1,even^1,nums,k); \n        long long notTake = nums[idx] + f(idx+1,even,nums,k);\n\n        return dp[idx][even] = max(take,notTake);\n    }\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        memset(dp,-1,sizeof(dp));\n        return f(0,1,nums,k);\n    }\n};\n```\n\n# Tabulation\n```\nclass Solution {\nprivate:\n    long long dp[20002][2];\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        int n = nums.size();\n        memset(dp,0,sizeof(dp));\n        // base cases\n        dp[n][0] = -1e9;\n        dp[n][1] = 0;\n        for(int idx=n-1;idx>=0;--idx) {\n            for(int even=0;even<2;++even) {\n                long long take = (nums[idx]^k) + dp[idx+1][even^1]; \n                long long notTake = nums[idx] + dp[idx+1][even];\n\n                dp[idx][even] = max(take,notTake);\n            }\n        }\n        return dp[0][1];        \n    }\n};\n```\n\n# Space-Optimized Tabulation (2 dp array)\n```\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> curr(2,0),next(2,0);\n        // base cases\n        next[0] = -1e9;\n        next[1] = 0;\n        for(int idx=n-1;idx>=0;--idx) {\n            for(int even=0;even<2;++even) {\n                long long take = (nums[idx]^k) + next[even^1]; \n                long long notTake = nums[idx] + next[even];\n\n                curr[even] = max(take,notTake);\n            }\n            next = curr;\n        }\n        return curr[1];        \n    }\n};\n```\n\n# Space Optimized Tabulation (1 dp array)\n```\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> curr(2,0);\n        // base cases\n        curr[0] = -1e9;\n        curr[1] = 0;\n        for(int idx=n-1;idx>=0;--idx) {\n            long long take1 = (nums[idx]^k) + curr[1]; \n            long long notTake1 = nums[idx] + curr[0];\n\n            long long take2 = (nums[idx]^k) + curr[0]; \n            long long notTake2 = nums[idx] + curr[1];\n\n            curr[0] = max(take1,notTake1);\n            curr[1] = max(take2,notTake2);\n        }\n        return curr[1];        \n    }\n};\n```\n\n\nHope you found this helpful\nIf so please do Upvote it\nHappy Coding!!\n\n![leetcode.png](https://assets.leetcode.com/users/images/7a98ada3-fb9b-4413-8538-92fe790f4577_1701070150.1852815.png)\n\n
['Dynamic Programming', 'Tree', 'C++']