C++ O(N) time, O(1) space
Intuition\n1. First idea is that we can xor any pair of nodes in the tree, not only directly connected ones. Explanation: the tree is connected (as per descript
# Intuition\n1. First idea is that we can xor any pair of nodes in the tree, not only directly connected ones. Explanation: the tree is connected (as per description), thus, there always exists a path between nodes `a` and `b`: `a -> ... -> b`. Short reminder: `x^k^k = x`.By xor\'ing every pair on the path, we have:\n    1. `a^k -> x1^k -> x2 -> ... -> xn -> b`\n    2. `a^k -> x1 -> x2^k -> ... -> xn -> b`\n    3. `...`\n    4. `a^k -> x1 -> x2 -> ... -> xn^k -> b`\n    5. `a^k -> x1 -> x2 -> ... -> xn -> b^k`\n2. Second idea: total number of xor operations should be even, as we always change nodes in pairs. I.e. we are allowed to xor only 0 (do not touch tree at all), 2, 4, ..., 2*m nodes. So, we traverse all node values in `nums`, and keep two results: `result` (current best result achieved with even count of xor operations) and `alt_result` (current best result achieved with odd count of xor operations). For every `n` from `nums` we update both `result` and `alt_result`:\n    1. `result` = `max` of { `result + n` (still even number of xors), `alt_result + n^k` (odd number of xors + 1 more xor = even number of xors) }\n    2. `alt_result` = `max` of { `alt_result + n` (still odd number of xors), `result + n^k` (even number of xors + 1 more xor = odd number of xors) }\n\n\n# Complexity\n- Time complexity: O(N)\n- Space complexity: O(1)\n\n# Code\n```\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        long long result = 0, alt_result = -1e9;\n        for (auto n : nums) {\n            int alt_n = n ^ k;\n            long long tmp = result;\n            result = max(result + n, alt_result + alt_n);\n            alt_result = max(alt_result + n, tmp + alt_n);\n            //cout << result << "," << alt_result << endl;\n        }\n        return result;\n    }\n};\n```
['C++']