An undirected tree has nodes numbered 0 through nums.length - 1. Node i starts with value nums[i], and each pair in edges connects two nodes.
In one operation, choose an edge [u, v] and replace both endpoint values with their bitwise XOR with k: nums[u] = nums[u] XOR k and nums[v] = nums[v] XOR k. You may repeat this operation on any edges, including choosing the same edge more than once.
Return the largest possible sum of all node values after any number of operations, including zero.
Diagram nodes show node index:value.
Example 1:
Input: nums = [0,0]
k = 5
edges = [[0,1]]
Output: 10Explanation: Choose the only edge. Both endpoint values change from 0 to 5, giving the maximum sum of 10.
Example 2:
Input: nums = [1,7,1]
k = 3
edges = [[0,1],[1,2]]
Output: 11Explanation: Choose edge [0,1] and then edge [1,2]. The middle node is changed twice and returns to 7, while both end nodes become 2. The final values [2,7,2] sum to 11.
Example 3:
Input: nums = [7,7]
k = 3
edges = [[0,1]]
Output: 14Explanation: Changing the only edge makes both values 4 and lowers the sum to 8. Performing no operations keeps the maximum sum of 14.
Constraints:
2 <= nums.length <= 200000 <= nums[i] <= 10000000001 <= k <= 1000000000edges.length == nums.length - 1- Each edge contains two node indices between
0andnums.length - 1. - The edges form a valid undirected tree.