[C++ / Go] Greedily from Leaves and Sacrifice Chosen Root - O(n) time + O(1) space
Intuition\n## Optimize Greedily from Leaves and Sacrifice Chosen Root\n- Greedily optimize from leaves:\n    - Each node can either be num or num ^ k. To maximi
# Intuition\n## Optimize Greedily from Leaves and Sacrifice Chosen Root\n- Greedily optimize from leaves:\n    - Each node can either be `num` or `num ^ k`. To maximize the sum, we choose the more optimal value between `num` and `num ^ k`.\n    - Start the optimization process from the leaves, and move towards the parent nodes, continuously optimizing each node using its parent.\n    - This iterative optimization ensures that by the time we reach the root, all other nodes have been optimized, just the root remained unsure to be optimize.\n- Sacrifice chosen root:\n    - The root node is not fixed initially so we can choose any node to be the root. \n    - The optimal root is the node where the difference between its value and the value after applying the XOR operation is minimal. \n    - This root node can then be sacrificed to achieve the best overall optimization.\n## Optimize calculating process\n- Each node is used to optimize their children, and then its parent will optimize it\n=> Each node can be optimize independely to calculate optimize value and add to the total result.\n- For each operation, two nodes will be changed so the total number of changed nodes always is even number.\n    - After optimize independely all nodes, if the numbers of change nodes is even then the root is also optimized.\n    - Else the root is not optimized and we have to sacrifice it.\n\n# Approach\n- For each nodes with value `num`:\n    - If `num < num ^ k`:\n        - This node will be changed.\n        - Total result is added by `num ^ k`\n    - Else\n        - This node is optimized already\n        - Total result is added by `num`\n    - Keep track of minimum difference of `num` and `num ^ k` for sacrificing if needed.\n- After optimize independely all nodes:\n    - If the numbers of change nodes is even then the root is also optimized, return current total result.\n    - Else return current total result - minimum difference node.\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(1)$\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        long long res = 0;\n        int changes = 0;\n        int minDiff = INT_MAX;\n        \n        for (int num : nums) {\n            int xorNum = num ^ k;\n\n            if (num < xorNum) {\n                changes++;\n                res += xorNum;\n            } else {\n                res += num;\n            }\n\n            minDiff = min(minDiff, abs(num - xorNum));\n        }\n\n        if (changes % 2 == 1)\n            return res - minDiff;\n        else\n            return res;\n    }\n};\n```\n```Go []\nfunc maximumValueSum(nums []int, k int, edges [][]int) int64 {\n    var res int64\n    changes := 0\n    minDiff := math.MaxInt32\n\n    for _, num := range nums {\n        xorNum := num ^ k\n\n        if num < xorNum {\n            changes++\n            res += int64(xorNum)\n        } else {\n            res += int64(num)\n        }\n\n        diff := abs(num - xorNum)\n        if diff < minDiff {\n            minDiff = diff\n        }\n    }\n\n    if changes % 2 == 1 {\n        return res - int64(minDiff)\n    } else {\n        return res\n    }\n}\n\nfunc abs(a int) int {\n    if a < 0 {\n        return -a\n    }\n    return a\n}\n```
['Greedy', 'C++', 'Go']