Python, O(n), no edges needed, with intuition
Intuition\nWe could think of our problem in next way: for each node we can take either nums[i] or nums[i]^k into the sum. We can think of node as being in even 
# Intuition\nWe could think of our problem in next way: for each node we can take either `nums[i]` or `nums[i]^k` into the sum. We can think of node as being in `even` and `odd` (modified) states. That is some `2**n` combinations. However some combinations are invalid. \n\nWe can prove, that required and sufficient condition for a combination to be valid is next:\nAmout of `nums[i]^k` is *even*. \nMore formally - combination will be valid iff amount of `odd` nodes is *even*. \n\nRequired part: is obvious by nature of operation. Since we always change one edge (2 nodes), we always flip the state of two nodes, so \nparity of `odd` nodes is invariant (and intially it\'s even). \n\nSufficient part: since we have a tree, by definition there is always a path between *ANY* `i` and `j` nodes. So we can always revert *ANY* `i` and `j` (not only neighbors) by just applying operation along each edge of a path `i->n1->n2->...->nk->j`. All nodes in between (`n1,...,nk`) will be get touched twice (left in the same state since `(x^k)^k==x`), and `i` and `j` will get touched once (both flip it\'s states). So as long as amount of `odd` nodes is even (we could form pairs) - we can flip them and reach initial state. Which proves any such state can be reached from initial state.\n\n**That drives us to conclusion - we don\'t care about the edges structure at all.**\n\nSo, we just need to find `max sum` over all `even` combinations (subsets). `Odd` subset is a subset that has odd amount of odd nodes, `even` subset - even amount of `odd` nodes (or odd amount of `1`s in it\'s binary representation if thinking `1==odd`, `0==even`).\n\nThat is kind of classical DP problem.\n\n\n# Approach\nDriven by intuition, instead of DP array we just use two variables (`so`,`se`) which hold maximum sums at current step for `odd` and `even` subsets.\n- at each step we take `odd` and `even` element (`o`, `e`) and update sums accordingly, picking best option.\n- we can get `odd` sum by adding `odd` elemen to `even` sum or adding `even` element to `odd` sum.\n- we can get `even` sum by  adding `even` element to `even` sum or adding `odd` element to `odd` sum.\n- initially we can\'t have `odd` sum, and `even` sum is `0`.\n\n# Complexity\n- Time complexity: `O(n)`\n- Space complexity: `O(1)`\n\n# Code\n```\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        so,se=float(\'-inf\'),0\n        for n in nums:\n            o,e=n^k,n\n            so,se=max(so+e,se+o),max(so+o,se+e)\n        return se\n```\n1-liner\n```\nclass Solution:\n    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:\n        return reduce(lambda acc,n:(max(acc[0]+n,acc[1]+(n^k)),max(acc[0]+(n^k),acc[1]+n)), nums, (float(\'-inf\'), 0))[1]\n\n```
['Dynamic Programming', 'Python3']