最大节点价值之和

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 nodes u and v, and update their values as follows:
  • nums[u] = nums[u] XOR k
  • nums[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: 6
Explanation: Alice can achieve the maximum sum of 6 using a single operation:
- Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -> [2,2,2].
The total sum of values is 2 + 2 + 2 = 6.
It can be shown that 6 is the maximum achievable sum of values.

Example 2:

Input: nums = [2,3], k = 7, edges = [[0,1]]
Output: 9
Explanation: Alice can achieve the maximum sum of 9 using a single operation:
- Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -> [5,4].
The total sum of values is 5 + 4 = 9.
It can be shown that 9 is the maximum achievable sum of values.

Example 3:

Input: nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
Output: 42
Explanation: The maximum achievable sum is 42 which can be achieved by Alice performing no operations.

 

Constraints:

• 2 <= n == nums.length <= 2 * 104
• 1 <= k <= 109
• 0 <= nums[i] <= 109
• 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.

/*
 * 思路：
 * - 给定无向树中的节点和边，以及一个整数 k。
 * - 我们可以通过选择任意边来操作两个节点的值：nums[u] = nums[u] XOR k, nums[v] = nums[v] XOR k。
 * - 目标是通过多次操作，使得所有节点的价值和最大化。
 * - 由于 XOR 操作的性质，我们可以分别计算不进行操作时的价值和（sumOriginal），
 *   以及每个节点 XOR k 后的价值和（sumXorAll）。
 * - 最终的结果为 sumOriginal 和 sumXorAll 的较大值。
 */
import java.util.Arrays;

public class Solution {
    public int maxSumAfterOperations(int[] nums, int k, int[][] edges) {
        int sumOriginal = Arrays.stream(nums).sum();
        int sumXorAll = Arrays.stream(nums).map(num -> num ^ k).sum();
        return Math.max(sumOriginal, sumXorAll);
    }
}

此题解采用对每个节点计算XOR操作后与原始值的差值来决定是否进行操作。首先计算整个树节点的初始总价值。然后，对于每个节点，计算执行一次XOR操作后的新价值与原始价值的差值，将所有正差值（代表XOR后价值提高）存储在列表a中，所有非正差值（代表XOR后价值不变或减少）存储在列表b中。如果a的长度是偶数，直接将所有a中的差值加到总价值中即可，因为我们可以选择边来确保执行XOR的次数对于所有提高价值的节点都是偶数次。如果a的长度是奇数，需要移除一个最小的正差值（即最少的价值提升）来使剩余操作次数为偶数，同时也考虑通过执行一次对于价值降低或不变节点的操作来获取可能的最大值。最终，比较这两种策略得到的价值，选择较大的一个。

O(n)

O(n)