DFS from any vertex
Intuition\nEven number of XOR is the same as no XOR, odd number of XOR is the same as 1 XOR. We can do DFS on the graph and try to find max between two cases. I
# Intuition\nEven number of XOR is the same as no XOR, odd number of XOR is the same as 1 XOR. We can do DFS on the graph and try to find max between two cases. It does not matter which node to start with. This one is hard to prove, but its easy to see empyrically once code is ready.\n\n# Approach\nDFS on the graph with keeping track of two cases: with even and odd number of XORs applied at a given Vertice. Return max result with even and odd number of XORs.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        # returns max result without xor and with xor applied\n        # on the value of the vertice at index "index"\n        def dfs(graph, index, visited):\n            visited[index] = True\n            no_xor, xor = nums[index], nums[index] ^ k\n            # maximum sum, number xors used, minimal diff\n            max_sum, num_xors, min_diff = 0, 0, abs(no_xor - xor)\n            if xor > no_xor:\n                max_sum = xor\n                num_xors = 1\n            else:\n                max_sum = no_xor\n            for neigh in graph[index]:\n                if not visited[neigh]:\n                    no_xor, xor = dfs(graph, neigh, visited)\n                    min_diff = min(min_diff, abs(no_xor - xor))\n                    # add to max_sum and increment xor number\n                    # if the bigger value comes from xor of child\n                    if xor > no_xor:\n                        max_sum += xor\n                        num_xors += 1\n                    else:\n                        max_sum += no_xor\n            # if we have even number of xors, we can use max_sum as result w/o xor\n            # and max_sum - min_diff a result with xor (with even number of xors)\n            if num_xors % 2 == 0:\n                return max_sum, max_sum - min_diff\n            # inverse case\n            else:\n                return max_sum - min_diff, max_sum\n        # build graph\n        graph = defaultdict(list)\n        n = len(nums)\n        for fr, to in edges:\n            graph[fr].append(to)\n            graph[to].append(fr)\n        # return case with even number of xors\n        return dfs(graph, 0, [False] * n)[0]\n```
['Python3']