Java Solution for Find the Maximum Sum of Node Values Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe key idea is to maximize the sum of node values by strategically deciding whether to
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key idea is to maximize the sum of node values by strategically deciding whether to perform XOR operations on connected nodes. In a linear structure (like an array), this would involve deciding for each element whether to XOR it with a given value k.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tInitialization:\n\t\u2022\tMemoization Array: memo is used to store results for subproblems to avoid redundant calculations.\n\t\u2022\tDFS Traversal: The function dfs traverses the nodes starting from node 0 and considers both the scenarios: applying XOR and not applying XOR.\n2.\tRecursive Function dfs:\n\t\u2022\tBase Case: If node equals the length of nums, it returns 0 if isEven is 1 (indicating an even number of operations) or Integer.MIN_VALUE if isEven is 0.\n\t\u2022\tMemoization Check: If the result for the current node and state (even/odd) is already computed, return the stored result.\n\t\u2022\tCompute No XOR Case: Calculate the sum if no XOR operation is performed on the current node.\n\t\u2022\tCompute XOR Case: Calculate the sum if XOR operation is performed on the current node.\n\t\u2022\tMemoize and Return: Store the maximum of the above two sums in the memoization array and return it.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tDFS Traversal: Each node is visited once, and for each node, we make decisions based on its children.\n\u2022\tMemoization: The memo array stores results for each node with two possible states (even/odd).\n\u2022\tTotal time complexity is O(n) because we visit each node once and perform constant-time operations.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tMemoization Array: The memoization array has a size of O(n \\times 2) = O(n).\n\u2022\tCall Stack: The recursive DFS call stack can go as deep as the number of nodes in the tree, which is O(n) in the worst case.\n\u2022\tTotal space complexity is O(n).\n\n# Code\n```\nclass Solution {\n    public long maximumValueSum(int[] nums, int k, int[][] edges) {\n        // Build the adjacency list for the tree\n        int n = nums.length;\n        \n        // Initialize memoization array\n        long[][] memo = new long[n][2];\n        for (long[] row : memo) {\n            Arrays.fill(row, -1);\n        }\n        \n        // Call the helper function to calculate the max sum starting from node 0\n        return dfs(0, 1, nums, k, memo);\n    }\n\n    private long dfs(int node, int isEven, int[] nums, int k, long[][] memo) {\n        if (node == nums.length) {\n            return isEven == 1 ? 0 : Integer.MIN_VALUE;\n        }\n\n        if (memo[node][isEven] != -1) {\n            return memo[node][isEven];\n        }\n\n        long noXorDone = nums[node] + dfs (node + 1, isEven, nums, k, memo);\n\n        long xorDone = (nums[node] ^ k) + dfs (node + 1, isEven ^ 1, nums, k, memo);  \n        \n        \n        return memo[node][isEven] = Math.max(xorDone, noXorDone);\n    }\n}\n```
['Java']