✅ Beat 100% | ✨ O(n) O(1) | 🏆 Most Efficient Solution | 💯 One pass with Easy to Read code.
Intuition\n Describe your first thoughts on how to solve this problem. \n  * Each node is like a toggle button, when we push it, its value becomes x XOR k; when
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n  * Each node is like a toggle button, when we push it, its value becomes `x XOR k`; when we push it again, it\'s value becomes `x XOR k XOR k = x`. Yes it recovers its original value!\n  * We are allowed to push two buttons that are adjacent in the graph. However, we can choose any path $a_1 \\rightarrow a_2 \\rightarrow a_3$ and apply the operations on both $a_1 \\leftrightarrow a_2$ and $a_2 \\leftrightarrow a_3$, and end result is that $a_2$ recovers while $a_1$ and $a_3$ is pushed. We can extend the path to any length to connect **any** two nodes and push them at the same time. This means we can choose push **any** group of even number of nodes.\n  * When we push a button, we *gain* some value to the total sum, which is `(x XOR k) - x`. If this *gain* is positive, we consider it a `gain`. Otherwise, we consider it a `lost` (negative of the *gain*)\n  * The optimal solution, at this point, is intuitively to:\n    * pick *all* the `gain`s if the count of `gain`s is even, or if it\'s odd, we pick the best of the following two:\n    * pick all the `gain`s except the smallest `gain`\n    * pick all the `gain`s *and* the smallest `lost`\n  * Edges are not needed. As long as the graph is connected we can always reach the optimal solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe run through the `nums` array once to gather the necessary stats:\n  * `sum`: sum of `nums` + all `gain`\n  * `smallest_gain`: the smallest `gain` (positive *gain*)\n  * `smallest_lost`: the smallest `-gain` (negative *gain*)\n  * `gain_count`: the number of `gain`\n\nAnd then we apply the optimal solution.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$\\Theta(n)$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$\\Theta(1)$\n\n# Code\n```\nclass Solution {\npublic:\n  long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n    int64_t sum = 0;\n    int smallest_gain = 2 * k + 1;\n    int smallest_lost = 2 * k + 1;\n    int gain_count = 0;\n    for (int num : nums) {\n      int gain = (num ^ k) - num;\n      if (gain > 0) {\n        smallest_gain = min(smallest_gain, gain);\n        sum += num + gain;\n        ++gain_count;\n      } else {\n        smallest_lost = min(smallest_lost, -gain);\n        sum += num;\n      }\n    }\n    if (gain_count % 2 == 1) {\n      sum -= min(smallest_gain, smallest_lost);\n    }\n    return sum;\n  }\n};\n```
['Math', 'C++']