DP recurion+memo->tabular->space O(1)||119ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nQuestion is hard. Use DP to solve. edges is ignored!\nDP recurion+memo->tabular->optimi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nQuestion is hard. Use DP to solve. `edges` is ignored!\nDP recurion+memo->tabular->optimized space\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet `0` be the root.\nLet `f(i, c)=dp[i][c]` denote the max sum from the root to i where `c`  is the number (modulo 2) of XORing operations applied.\n\nThe hardest part is to find the recursive relation between vertices `i` & `i+1`. Since LC says that this undirected graph is a tree, there exists always a path between `i` & `i+1`. An operation is applied, then 2 operations for XORing with `k` are done.\n```\n# Let x=nums[i], consider not taking x^k , taking x^k\nf(i, c)= max(x+f(i+1, c),(x^k)+f(i+1,1-c)) \n```\nXoring is performing in pair, for base case, let `n=len(nums)`,\n```\nif i==n:\n# invalid path, any negative integer with large enough absolute value\n    if c==1: return -(1<<31) \nreturn 0 # base case\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(n)\\to O(1)$$\n# Codes: Recursion+Memo||C++ 149ms Beats 96.44%\n```Python []\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        n=len(nums)\n        @cache\n        def f(i, c):\n            if i==n:\n                if c==1: return -(1<<31)\n                return 0\n            x=nums[i]\n            return max(x+f(i+1, c),(x^k)+f(i+1,1-c))\n        return f(0, 0)\n        \n```\n```C++ []\nclass Solution {\npublic:\n    int n, k;\n    long long dp[20000][2];\n    long long f(int i, bool c, vector<int>& nums ){\n        if (i==n) return (c)?INT_MIN:0;\n        if (dp[i][c]!=-1) return dp[i][c];\n        long long x=nums[i]; \n        return dp[i][c]=max(x+f(i+1,c, nums), (x^k)+f(i+1,!c, nums));\n    }\n    \n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        n=nums.size();\n        this->k=k;\n        fill(&dp[0][0], &dp[0][0]+20000*2, -1);\n        return f(0, 0, nums);\n    }\n};\n\n```\n# C++ iterative DP||139ms Beats 98.89%\nRewrite the top-down design to bottom-up solution\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        int n=nums.size();\n        long long dp[20001][2]={0};\n        dp[n][0]=0, dp[n][1]=INT_MIN;\n        for(int i=n-1; i>=0; i--){\n            long long x=nums[i];\n            for ( int c=0; c<=1; c++)\n                dp[i][c]=max(x+dp[i+1][c], (x^k)+dp[i+1][!c]);\n        }\n\n        return dp[0][0];\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Code with optimized space||153ms Beats 96.44%\n\nUsing the trick `&1` same as `%2`\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        int n=nums.size();\n        long long dp[2][2]={0};\n        dp[n&1][0]=0, dp[n&1][1]=INT_MIN;\n        for(int i=n-1; i>=0; i--){\n            long long x=nums[i];\n            for (int c=0; c<=1; c++)\n                dp[i&1][c]=max(x+dp[(i+1)&1][c], (x^k)+dp[(i+1)&1][!c]);\n        }\n        return dp[0][0];\n    }\n};\n\n```\n# C++ dual version\nbase case: `dp[0][0]=0, dp[0][1]=INT_MIN`\nrecursion: `x=nums[i-1]` ,`dp[i&1][c]=max(x+dp[(i-1)&1][c], (x^k)+dp[(i-1)&1][!c]);`\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    static long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) \n    {\n        const int n=nums.size();\n        long long dp[2][2]={0};\n        dp[0][0]=0, dp[0][1]=INT_MIN;\n        for(int i=1; i<=n; i++){\n            long long x=nums[i-1];\n            for (int c=0; c<=1; c++)\n                dp[i&1][c]=max(x+dp[(i-1)&1][c], (x^k)+dp[(i-1)&1][!c]);\n        }\n        return dp[n&1][0];\n    }\n};\n```\n# C++ optimpized version||119ms beats 100%\n\nThanks to @Sergei99, an optimized version using just variables is done.\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    static long long maximumValueSum(vector<int>& nums, const int k, vector<vector<int>>& edges) \n    {\n        const int n=nums.size();\n        long long dp0=0, dp1=INT_MIN;\n        for(int i=1; i<=n; i++){\n            const long long x=nums[i-1], xk=x^k;\n            const long long dp_0=max(x+dp0, xk+dp1);\n            dp1=max(x+dp1, xk+dp0);\n            dp0=dp_0;\n        }\n        return dp0;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Dynamic Programming', 'C++', 'Python3']