Greedy Sacrifice
\nIn a tree, we can freely change any even number of nodes.\n\n> I got this intuitioin by drawing a few trees and trying to change some nodes without changing t
\nIn a tree, we can freely change any even number of nodes.\n\n> I got this intuitioin by drawing a few trees and trying to change some nodes without changing the others.\n    \nSo, we count nodes that we want to change (where n ^ k > n).\n    \nIf the count is even, we just return the best `sum`.\n    \nIf the count is odd, we need to `sacrifice` one node:\n- Do not change a node we want to change, or\n- Change a node that we do not want to change.\n    \nWe track the smallest sacrifice `min(abs(n - (n ^ k))`, and subtract it from the best `sum`.\n\n**Python 3**\n```python\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        best_sum = sum(max(n, k ^ n) for n in nums)\n        cnt = sum((n ^ k) > n for n in nums)  \n        return best_sum - (min(abs(n - (n ^ k)) for n in nums) if cnt % 2 else 0)\n```\n**C++** \n```cpp\nlong long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n    long long sum = 0, cnt = 0, sacrifice = INT_MAX;\n    for (long long n : nums) {\n        sum += max(n ^ k, n);\n        cnt += (n ^ k) > n;\n        sacrifice = min(sacrifice, abs(n - (n ^ k)));\n    }\n    return sum - (cnt % 2 ? sacrifice : 0);\n}\n```\n\n\n
['C', 'Python3']