Insight into XOR | Full explaination with comments
Intuition\n- XOR is associative and commutative, meaning we can shift around the order it\'s applied and still get the same result.\n- If a single node has the 
# Intuition\n- XOR is associative and commutative, meaning we can shift around the order it\'s applied and still get the same result.\n- If a single node has the operation applied to it multiple times, (x XOR k) XOR k... each k XOR k pair will cancel to 0, and 0 XOR x is just x.\n  - In other words, if we apply the operation to the same node an even number of times, it will stay unchanged. If we apply it an odd number of times, then it will be the same as applying it once.\n- Each node in a tree is always connected to every other node in a tree.\n- Consider applying the operations to every edge along a path between two nodes. For every node which isn\'t the starting and ending node, the operation is applied for both the incoming and outgoing edge of the path. Since this is applying the operation an even number of times, it will leave those nodes unchanged.\n- Therefore we can pick any pair of nodes and decide to apply the XOR to just those two nodes.\n- This implies the best we can do is to pair all the nodes which will increase after the XOR is applied with each other. If there is one leftover, we can decide to pair it with the node which is decreased by the XOR the least if that\'s a net gain.\n\n# Approach\n- Sum the current node\'s values\n- Check the delta change when XOR is applied for each node and sort them based on this delta\n- Consider each positive delta as being paired and add them all to the total sum\n- If there are an odd number of positive gains, then check the last and smallest positive gain to see if it\'s worth pairing it with the smallest negative delta\n\n# Complexity\n- Time complexity: $$O(n*log(n))$$\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution\n{\npublic:\n\tlong long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges)\n\t{\n\t\t// In the first pass through the numbers we calculat the current total\n\t\t// and keep track of the deltas if the xor is applied to each node\n\t\tvector<int> negativeDeltas;\n\t\tvector<int> positiveDeltas;\n\t\tlong long ans = 0;\n\t\tfor (int n : nums)\n\t\t{\n\t\t\tans += n;\n\n\t\t\tint after = n ^ k;\n\t\t\tif (after > n)\n\t\t\t\tpositiveDeltas.push_back(after - n);\n\t\t\telse\n\t\t\t\tnegativeDeltas.push_back(n - after);\n\t\t}\n\n\t\t// We then sort the deltas to know which are the smallest\n\t\t// (could have used a heap as well, but in retrospect I realize a simple min could be tracked as well)\n\t\tsort(negativeDeltas.begin(), negativeDeltas.end());\n\t\tsort(positiveDeltas.begin(), positiveDeltas.end());\n\n\t\tbool evenNumPositives = positiveDeltas.size() % 2 == 0;\n\t\t// If there is a node which can be made greater, but can\'t be paired \n\t\t// (because there are an odd number of positive nodes)\n\t\t// then we can either not pair the smallest one, or\n\t\t// pair it with the smallest negative if the positive delta\n\t\t// outwieghs the negative delta.\n\t\tif (!evenNumPositives && !negativeDeltas.empty())\n\t\t{\n\t\t\tif (positiveDeltas[0] > negativeDeltas[0])\n\t\t\t\tans += positiveDeltas[0] - negativeDeltas[0];\n\t\t}\n\n\t\t// We always pair as many positives as we can, adding their deltas to the total\n\t\tfor (int i = evenNumPositives ? 0 : 1; i < positiveDeltas.size(); ++i)\n\t\t\tans += positiveDeltas[i];\n\n\t\treturn ans;\n\t}\n};\n```
['Math', 'Tree', 'C++']