# LeetCode 3068. Find the Maximum Sum of Node Values

https://leetcode.com/problems/find-the-maximum-sum-of-node-values/description/

## 題目大意

給一顆樹即其邊，每次取一個邊 `[u, v]` 對兩端節點 XOR `k`

- `nums[u] = nums[u`] XOR `k`
- `nums[v] = nums[v]` XOR `k`

上述操作可執行任意次，使節點總和之最大，求此最大值？

## 思考

首先要有兩個認知：

1. 對一個節點 XOR `k` 偶數次相當於沒變
2. 每次操作必定改變兩個節點的值

那麼想法就很暴力了，我們每次都記錄 XOR 後跟原來誰比較大，較大的就累加進 `sum`
同時，我們要記錄 XOR 後的結果被累加進去 `sum` 有幾次

當 `cnt` 是奇數次，那顯然不合我們前面的認知二，所以我們還要記錄最小的變化量，把他補回去

class Solution
{
public:
    long long maximumValueSum(vector<int> &nums, int k, vector<vector<int>> &edges)
    {
        long long sum = 0;
        int cnt = 0;
        int delta = INT_MAX;

        for (const int num : nums)
        {
            const int xorNum = num ^ k;
            sum += max(num, xorNum);
            cnt += (xorNum > num);
            delta = min(delta, abs(num - xorNum));
        }

        return (cnt % 2) ? sum - delta : sum;
    }
};

開頭說的兩個認知，是這題的關鍵，想通了要做也其實不難

這題我參考了下面這支影片前面的解說，他解釋得比較仔細

<center><iframe width="560" height="315" src="https://www.youtube.com/embed/bnBp6_b4GCw" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe></center>