> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find the Maximum Sum of Node Values

> Tested Python solution for LeetCode 3068 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 3068, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Dynamic Programming](/catalog/topics/dynamic-programming), [Greedy](/catalog/topics/greedy), [Bit Manipulation](/catalog/topics/bit-manipulation), [Tree](/catalog/topics/tree), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/find-the-maximum-sum-of-node-values/description/).

Generate this problem as a practice environment: tested reference solution, 21 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 3068   # by problem number
lcpy gen -s find_the_maximum_sum_of_node_values   # by problem name
```

## Problem

There exists an **undirected** tree with `n` nodes numbered `0` to `n - 1`. You are given a **0-indexed** 2D integer array `edges` of length `n - 1`, where `edges[i] = [u_i, v_i]` indicates that there is an edge between nodes `u_i` and `v_i` in the tree. You are also given a **positive** integer `k`, and a **0-indexed** array of **non-negative** integers `nums` of length `n`, where `nums[i]` represents the **value** of the node numbered `i`.

Alice wants the sum of values of tree nodes to be **maximum**, for which Alice can perform the following operation **any** number of times (**including zero**) on the tree:

* Choose any edge `[u, v]` connecting the nodes `u` and `v`, and update their values as follows:
  * `nums[u] = nums[u] XOR k`
  * `nums[v] = nums[v] XOR k`

Return the **maximum** possible **sum** of the **values** Alice can achieve by performing the operation **any** number of times.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012513.png)

```
Input: nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
Output: 6
Explanation: Alice can achieve the maximum sum of 6 using a single operation:
- Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -> [2,2,2].
The total sum of values is 2 + 2 + 2 = 6.
It can be shown that 6 is the maximum achievable sum of values.
```

![Example 2](https://assets.leetcode.com/uploads/2024/01/09/screenshot-2024-01-09-220017.png)

```
Input: nums = [2,3], k = 7, edges = [[0,1]]
Output: 9
Explanation: Alice can achieve the maximum sum of 9 using a single operation:
- Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -> [5,4].
The total sum of values is 5 + 4 = 9.
It can be shown that 9 is the maximum achievable sum of values.
```

![Example 3](https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012641.png)

```
Input: nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
Output: 42
Explanation: The maximum achievable sum is 42 which can be achieved by Alice performing no operations.
```

### Constraints

* `2 <= n == nums.length <= 2 * 10^4`
* `1 <= k <= 10^9`
* `0 <= nums[i] <= 10^9`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `0 <= edges[i][0], edges[i][1] <= n - 1`
* The input is generated such that `edges` represent a valid tree.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_maximum_sum_of_node_values/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_maximum_sum_of_node_values/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def maximum_value_sum(self, nums: list[int], k: int, edges: list[list[int]]) -> int:
        # A tree lets any even-sized set of nodes be XORed with k (each edge op
        # toggles two endpoints; paths transfer a toggle and cancel out).
        # So maximize the sum of gains (x ^ k) - x over an even count of nodes.
        del edges
        total = sum(nums)
        gains = sorted(((x ^ k) - x for x in nums), reverse=True)
        for i in range(0, len(gains) - 1, 2):
            pair = gains[i] + gains[i + 1]
            if pair <= 0:
                break
            total += pair
        return total
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.