3068. Find the Maximum Sum of Node Values - Explanation

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(len(nums))]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        def dfs(node, par):
            res = [nums[node], nums[node] ^ k]
            for child in adj[node]:
                if child == par:
                    continue

                cur = dfs(child, node)
                tmp = []
                tmp.append(max(res[0] + cur[0], res[1] + cur[1]))
                tmp.append(max(res[1] + cur[0], res[0] + cur[1]))
                res = tmp

            return res

        return dfs(0, -1)[0]

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        dp = [[None] * 2 for _ in range(len(nums))] + [[0, float("-inf")]]

        def dfs(i, xorCnt):
            if dp[i][xorCnt] is not None:
                return dp[i][xorCnt]

            res = nums[i] + dfs(i + 1, xorCnt)
            res = max(res, (nums[i] ^ k) + dfs(i + 1, xorCnt ^ 1))
            dp[i][xorCnt] = res
            return res

        return dfs(0, 0)

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        n = len(nums)
        dp = [[0, 0] for _ in range(n + 1)]
        dp[n][1] = float("-inf")

        for i in range(n - 1, -1, -1):
            dp[i][0] = max(nums[i] + dp[i + 1][0], (nums[i] ^ k) + dp[i + 1][1])
            dp[i][1] = max(nums[i] + dp[i + 1][1], (nums[i] ^ k) + dp[i + 1][0])

        return dp[0][0]

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        dp = [0, float("-inf")]

        for i in range(len(nums) - 1, -1, -1):
            next_dp = [0, 0]
            next_dp[0] = max(nums[i] + dp[0], (nums[i] ^ k) + dp[1])
            next_dp[1] = max(nums[i] + dp[1], (nums[i] ^ k) + dp[0])
            dp = next_dp

        return dp[0]

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        delta = [(num ^ k) - num for num in nums]
        delta.sort(reverse=True)
        res = sum(nums)

        for i in range(0, len(nums), 2):
            if i == len(nums) - 1:
                break
            path_delta = delta[i] + delta[i + 1]
            if path_delta <= 0:
                break
            res += path_delta

        return res

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        xorCnt = res = 0
        minDiff = 1 << 30

        for num in nums:
            xorNum = num ^ k
            if xorNum > num:
                res += xorNum
                xorCnt ^= 1
            else:
                res += num
            minDiff = min(minDiff, abs(xorNum - num))

        return res - xorCnt * minDiff