[Java/C++/Python] Edges are Useless
TLDR\nToo long don\'t read:\n\nThe shape of tree doesn\'t matter.\nedges are useless.\nEach operation, change two nodes,\nso in the end, we change whichever eve
# **TLDR**\nToo long don\'t read:\n\nThe shape of tree doesn\'t matter.\nedges are useless.\nEach operation, change two nodes,\nso in the end, we change whichever even nodes.\n<br>\n\n# **Intuition**\nAfter the previous excercise on the tree,\nI was confident to handle dfs on the tree.\n\nNow each node can XOR or stay the same.\nEasy, we can do dp on the tree with DFS.\n<br>\n\n\n# **Intuition 2**\nWait,\nactually each node can xor with its parent.\n\nAnd we can choose the bigger one in `max(a, a ^ k)`,\nand leave the problem to its parent.\nFinally the root will be `a` or `a ^ k`.\n<br>\n\n# **Intuition 3**\nWait wait,\nwill the root in a good status (changed to bigger)?\n\nEach time, we will change on one of `edges`,\nand this will flip two nodes.\nSo the changes nodes count will always be even.\n\nSo just need to know the number of nodes to change.\nIf it\'s even, we are even, great.\nIf it\'s odd, this is odd:\nwe need keep one from bigger or make one smaller.\n<br>\n\n\n# **Intuition 3**\nWait wait wait,\ntalking about the `edges`\nwe used `a` of nodes\' value for sure.\nwe used `k` to change the value, good.\nIt seems we don\'t need the `edges` at all,\nand any node can be the one (root).\n<br>\n\n# **Explanation**\nFor each node value `a`,\nwe can change it to `b = a ^ k`,\nso we add `max(a, b)` to result `res`.\n\nAlso we count the if it\'s `a < b`, if so `c ^= 1`,\nAlso we update minimum diff `d` between `a - b`.\n\n\nIn the end, we check if we make the change for even time.\nIf so, we return `res`,\nOtherwise we return `res - d`.\n<br>\n\n# **Complexity**\nTime `O(n)`\nSpace `O(1)`\n<br>\n\n**Java**\n```java\n    public long maximumValueSum(int[] A, int k, int[][] edges) {\n        long res = 0;\n        int d = 1 << 30, c = 0;\n        for (int a : A) {\n            int b = a ^ k;\n            res += Math.max(a, b);\n            c ^= a < b ? 1 : 0;\n            d = Math.min(d, Math.abs(a - b));\n        }\n        return res - d * c;\n    }\n```\n\n**C++**\n```cpp\n    long long maximumValueSum(vector<int>& A, int k, vector<vector<int>>& edges) {\n        long long res = 0;\n        int d = 1 << 30, c = 0;\n        for (int a : A) {\n            int b = a ^ k;\n            res += max(a, b);\n            c ^= a < b;\n            d = min(d, abs(a - b));\n        }\n        return res - d * c;\n    }\n```\n\n**Python**\n```py\n    def maximumValueSum(self, A: List[int], k: int, edges: List[List[int]]) -> int:\n        res = c = 0\n        d = 1 << 30\n        for a in A:\n            res += max(a, b:= a ^ k)\n            c ^= a < b\n            d = min(d, abs(a - b))\n        return res - d * c\n```\n
['C', 'Python', 'Java']