Find the Maximum Sum of Node Values
There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 0-indexed 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.
You are also given a positive integer k, and a 0-indexed array of non-negative integers nums of length n, where nums[i] represents the value of the node numbered i.
Alice wants the sum of values of tree nodes to be maximum, for which Alice can perform the following operation any number of times, including zero, on the tree:
- Choose any edge
[u, v]connecting the nodesuandv, and update their values as follows: nums[u] = nums[u] XOR knums[v] = nums[v] XOR k
Return the maximum possible sum of the values Alice can achieve by performing the operation any number of times.
Example 1
Input
nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]Output
6Choosing edge [0, 2] changes the array from [1, 2, 1] to [2, 2, 2], whose total sum is 6, which is maximum.
Example 2
Input
nums = [2,3], k = 7, edges = [[0,1]]Output
9Choosing edge [0, 1] changes the array from [2, 3] to [5, 4], whose total sum is 9, which is maximum.
Constraints
- 2 <= n == nums.length <= 2 * 10^4
- 1 <= k <= 10^9
- 0 <= nums[i] <= 10^9
- edges.length == n - 1
- edges[i].length == 2
- 0 <= edges[i][0], edges[i][1] <= n - 1
- The input is generated such that edges represent a valid tree.