Beats 99% ‎️‍🔥Python3 || Greedy solution with intuition and explanation ✅
Intuition\nAt first, the problem seems to constrain us to picking nodes from the given edges and consider them pairwise. We need a few key observations to appro
# Intuition\nAt first, the problem seems to constrain us to picking nodes from the given edges and consider them pairwise. We need a few key observations to approach this problem:\n\n1. **XOR with k is like a toggle:**  Either the node value will increase, or it will decrease. Observe that (x ^ a) ^ a = x. We want the maximum value from these two.\n2. **XORing a bunch of nodes connected by a path is the same as toggling the first and last nodes**:  \n\n    Consider a path a->b->c->d->e where we want to XOR each of the edges.\n\n    If we XOR each edge in a->b, b->c, c->d, d->e, what happens? **a is toggled once, b to d are flipped twice, d is toggled once.**\n\n    This means, we can **effectively pick any pair of nodes in the tree and treat them as connected via a single edge,** regardless of whether this edge is part of the edges list or not. The length of this path, how far they are does not matter either, as **we are only concerned about the maximum sum and do not care about the number of toggles.**\n\n3. **Even number of nodes in the final selection:** As we see above, even though we have simplified the edge requirement, we at least one edge, ie, **at least need a pair of nodes** to choose at each turn. We need to find the best possible even number of such nodes.\n4.  One way to do this is by greedily picking either each node\'s value, or value ^ k - whichever is higher. And then, if we have an odd number of node toggles having a higher value, remove, or rather, **sacrifice the smallest (toggled) value out of them to get the maximum possible XOR sum.**\n\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        changes = 0\n        min_sacrifice = inf\n        final = 0\n\n        for val in nums:\n            tmp = val ^ k\n            if tmp > val:\n                changes += 1\n                final += tmp\n                # cost of not changing this node\n                min_sacrifice = min(min_sacrifice, tmp - val)\n            else:\n                final += val\n                # cost of changing this node\n                min_sacrifice = min(min_sacrifice, val - tmp)\n\n        # if the number of changes is odd, smallest sacrifice from the sum to make it even\n        if changes % 2:\n            final -= min_sacrifice\n\n        return final\n\n```
['Python3']