Today’s problem

3068. Find the Maximum Sum of Node Values

Important: all the methods below are based on this fact: xor even times equals xor zero times.

Method 1: Tree DP

Intuition and Approach

In this problem, if we only consider one direction, e.g., from root to leaf, then the process will not have after effect (later decisions will not affect previous ones). Therefore, we can use DP to solve this problem.

The hardest part is the definition of the dp. As we have a prerequisite of a direction, a better way to define the dp formula is to exclude the effect of current node. Also, for each node, there are two status, as described above, each node can either xor odd times or even times.

Therefore, we have our DP definition. $dp[x][0/1]$ means the largest value the children of x can achieve when the node x is changed (1) or unchanged (0).

Now, for each child c of node x, we can do two operations: either do xor for both node x and c, or do not do xor for neither x nor c.

The dp formula of these two operations will be: (Note: the priority of $\oplus$ is lower than $+$, so it is very important to add a parentheses.)

Do the xor operation $dp[x][0] = max(dp[x][0] + dp[c][0] + nums[c], dp[x][0] + dp[c][1] + (nums[c] \oplus k))$. $dp[x][1] = max(dp[x][1] + dp[c][0] + nums[c], dp[x][1] + dp[c][1] + (nums[c] \oplus k))$.
NOT do the xor operation $dp[x][0] = max(dp[x][1] + dp[c][1] + nums[c], dp[x][1] + dp[c][0] + (nums[c] \oplus k))$. $dp[x][1] = max(dp[x][0] + dp[c][0] + nums[c], dp[x][0] + dp[c][0] + (nums[c] \oplus k))$.

Note that the dp[x][0] and dp[x][1] should be renewed at the same time.

Moreover, another important thing is the initialization of the dp array. For all $dp[x][1]$, we will give it a value of $-inf$, so that we can avoid the case when c is a leaf node and the number is $\oplus$ with k contributes to the $dp[x]$ array.

The final result will be $max((dp[0][0] + nums[0]), (dp[0][1] + (nums[0] ^ k)))$

Complexity

Time complexity: $O(N)$, N is the length of nums.

Space complexity: $O(N)$, N is the length of nums.

Code

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        n = len(nums)
        dp = [[0 for _ in range(2)] for _ in range(n)]
        for i in range(n):
            dp[i][1] = -10_000_000_000
      
        edge = [[] for _ in range(n)]

        for x,y in edges:
            edge[x].append(y)
            edge[y].append(x)

        def dfs(x, fa):
            for to in edge[x]:
                if to == fa:
                    continue
                dfs(to, x)

                c0 = max(dp[to][0] + nums[to], dp[to][1] + (nums[to] ^ k))
                c1 = max(dp[to][0] + (nums[to] ^ k), dp[to][1] + nums[to])
                dp[x][0], dp[x][1] = max(dp[x][0] + c0, dp[x][1] + c1), max(dp[x][1] + c0, dp[x][0] + c1)
      
        dfs(0,-1)
        return max((dp[0][0] + nums[0]), (dp[0][1] + (nums[0] ^ k)))

Method 2: Tree DP with better memory

Intuition and Approach

In the previous code, we find that the $dp[x]$ will only use two times. Once in calculating the result of $dp[x]$, once in calculating the result of $dp[fa]$.

Therefore, we can return the value of $dp[x][0]$ and $dp[x][1]$ to avoid the extra space of the dp array.

Complexity

Time complexity: $O(N)$, N is the length of nums.

Space complexity: $O(1)$.

Code

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        n = len(nums)
        edge = [[] for _ in range(n)]

        for x,y in edges:
            edge[x].append(y)
            edge[y].append(x)

        def dfs(x, fa):
            dp0,dp1 = 0,-1e9
            for to in edge[x]:
                if to == fa:
                    continue
                c0, c1 = dfs(to, x)
                dp0, dp1 = max(dp0 + c0, dp1 + c1), max(dp0 + c1, dp1 + c0)
          
            return max(dp0 + nums[x], dp1 + (nums[x] ^ k)), max(dp0 + (nums[x] ^ k), dp1 + nums[x])
      
        return dfs(0,-1)[0]

Important: all the methods below are based on this fact: there are always a path between two nodes on a tree. Therefore, we can $\oplus$ all the nodes on this path, resulting the $\oplus$ of any two nodes on the tree.

Method 3: DP without tree

Intuition and Approach

For each node, we have two status, whether to $\oplus$ k or not. Therefore, the definition of the DP array will be: $dp[i][0/1]$ means whether there are odd (1) or even (0) $\oplus$ k operations when traversing to the ith node.

We then have the formular:

When this node $\oplus$ with k: $dp[i][0] = max(dp[i-1][0] + nums[i], dp[i-1][1] + (nums[i] ^ k))$
When this node do not $\oplus$ with k: $dp[i][1] = max(dp[i-1][1] + nums[i], dp[i-1][0] + (nums[i] ^ k))$

Note that there are always even $\oplus$ operations, so the answer would be $dp[n-1][0]$.

Complexity

Time complexity: $O(N)$, N is the length of nums.

Space complexity: $O(N)$, N is the length of nums.

Code

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        n = len(nums)
        dp = [[0 for _ in range(2)] for _ in range(n)]
        dp[0][0] = nums[0]
        dp[0][1] = (nums[0] ^ k)
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0] + nums[i], dp[i-1][1] + (nums[i] ^ k))
            dp[i][1] = max(dp[i-1][0] + (nums[i] ^ k), dp[i-1][1] + nums[i])
        return dp[-1][0]

Method 4: DP without tree with better memory

Intuition and Approach

Same as Method 2, we also find out that the dp[i] formular only use twice. In this case, we can use two variables instead of the whold array to have a better memory usage.

Also, the $max$ operations is too slow in python, so a better way is to use if else equations instead of max.

Complexity

Time complexity: $O(N)$, N is the length of nums.

Space complexity: $O(1)$.

Code

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        n = len(nums)
        dp0, dp1 = 0, -10_000_000_000
        for i in range(n):
            a = nums[i]
            b = a ^ k
            new_dp0 = dp0 + a if dp0 + a > dp1 + b else dp1 + b
            new_dp1 = dp0 + b if dp0 + b > dp1 + a else dp1 + a
            dp0, dp1 = new_dp0, new_dp1
        return dp0

Method 5: Greedy algorithm

Intuition and Approach

Another way to look at this method without of tree is using greedy algorithm. Because we know that we can $\oplus$ k as long as we can find a pair of nodes, we can use greedy algorithm to find the pairs that has the most differences after $\oplus$ k.

That is, we can first $\oplus$ every element with k, calculating the difference between the new array and the previous array, then find all the pairs that has a difference that is larger than zero, then we get our answer.

Complexity

Time complexity: $O(N)$, N is the length of nums.

Space complexity: $O(N)$, N is the length of nums.

Code

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        ans = sum(nums)
        diff = [(x ^ k) - x for x in nums]
        cnt,l,r = 0,inf,-inf
        for x in diff:
            if x > 0:
                cnt += 1
                if x < l:
                    l = x
                ans += x
            else:
                if r < x:
                    r = x
      
        if cnt % 2 == 1:
            ans += max(-l, r)
      
        return ans

~~I don’t know why using sort to do greedy algorithm is so neat and fast. Just as the one in the official solution.~~

For more solutions, please visit My blog

LeetCode Daily Question 2025-05-23

Today’s problem

Important: all the methods below are based on this fact: xor even times equals xor zero times.

Method 1: Tree DP

Intuition and Approach

Complexity

Code

Method 2: Tree DP with better memory

Intuition and Approach

Complexity

Code

Important: all the methods below are based on this fact: there are always a path between two nodes on a tree. Therefore, we can $\oplus$ all the nodes on this path, resulting the $\oplus$ of any two nodes on the tree.

Method 3: DP without tree

Intuition and Approach

Complexity

Code

Method 4: DP without tree with better memory

Intuition and Approach

Complexity

Code

Method 5: Greedy algorithm

Intuition and Approach

Complexity

Code

Advertisement

Today’s problem#

Important: all the methods below are based on this fact: xor even times equals xor zero times.#

Method 1: Tree DP#

Intuition and Approach#

Complexity#

Code#

Method 2: Tree DP with better memory#

Intuition and Approach#

Complexity#

Code#

Important: all the methods below are based on this fact: there are always a path between two nodes on a tree. Therefore, we can $\oplus$ all the nodes on this path, resulting the $\oplus$ of any two nodes on the tree.#

Method 3: DP without tree#

Intuition and Approach#

Complexity#

Code#

Method 4: DP without tree with better memory#

Intuition and Approach#

Complexity#

Code#

Method 5: Greedy algorithm#

Intuition and Approach#

Complexity#

Code#

Advertisement#

Today’s problem

Important: all the methods below are based on this fact: xor even times equals xor zero times.

Method 1: Tree DP

Intuition and Approach

Complexity

Code

Method 2: Tree DP with better memory

Intuition and Approach

Complexity

Code

Important: all the methods below are based on this fact: there are always a path between two nodes on a tree. Therefore, we can $\oplus$ all the nodes on this path, resulting the $\oplus$ of any two nodes on the tree.

Method 3: DP without tree

Intuition and Approach

Complexity

Code

Method 4: DP without tree with better memory

Intuition and Approach

Complexity

Code

Method 5: Greedy algorithm

Intuition and Approach

Complexity

Code

Advertisement