3068. 找到节点值的最大和

Hard

题目描述

存在一个有 n 个节点的无向树，节点编号为 0 到 n - 1。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个正整数 k，以及一个长度为 n 的非负整数数组 nums，其中 nums[i] 表示编号为 i 的节点的值。

Alice 希望树节点值的总和最大化，为此 Alice 可以在树上执行以下操作任意次数（包括零次）：

选择连接节点 u 和 v 的任意边 [u, v]，并按如下方式更新它们的值：
- nums[u] = nums[u] XOR k
- nums[v] = nums[v] XOR k

返回 Alice 通过执行操作任意次数能够实现的节点值的最大可能总和。

示例 1：

输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：Alice 可以通过一次操作实现最大总和 6：
- 选择边 [0,2]。nums[0] 和 nums[2] 变为：1 XOR 3 = 2，数组 nums 变为：[1,2,1] -> [2,2,2]。
值的总和为 2 + 2 + 2 = 6。
可以证明 6 是可实现的最大值总和。

示例 2：

输入：nums = [2,3], k = 7, edges = [[0,1]]
输出：9
解释：Alice 可以通过一次操作实现最大总和 9：
- 选择边 [0,1]。nums[0] 变为：2 XOR 7 = 5，nums[1] 变为：3 XOR 7 = 4，数组 nums 变为：[2,3] -> [5,4]。
值的总和为 5 + 4 = 9。
可以证明 9 是可实现的最大值总和。

示例 3：

输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
输出：42
解释：最大可实现总和为 42，Alice 无需执行任何操作即可实现。

约束：

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
输入保证 edges 表示一个有效的树

解题思路

这道题的关键洞察是：每次操作会对一条边的两个端点同时进行 XOR k 运算。我们需要理解操作的本质。

核心观察：

每次选择一条边操作，会同时改变两个节点的值
如果我们对同一条边操作偶数次，相当于没有操作（XOR 的性质）
最终状态可以看作：每个节点要么被 XOR k，要么保持原值

关键发现： 由于树的连通性，我们可以通过一系列操作让任意数量的节点被 XOR k，但有一个约束：被 XOR k 的节点数量必须是偶数个。

这是因为：每次操作改变两个节点的状态，所以状态改变的节点总数永远是偶数。

算法思路：

计算每个节点 XOR k 后的增益：gain[i] = (nums[i] XOR k) - nums[i]
将增益按降序排序
贪心选择：优先选择增益最大的偶数个节点进行 XOR 操作
如果选择奇数个正增益节点能获得更大收益，需要额外考虑一个负增益最小的节点

推荐解法：贪心算法 时间复杂度较低，思路清晰，易于实现。

代码实现

class Solution {
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        int n = nums.size();
        vector<long long> gains;
        long long totalSum = 0;
        
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
            gains.push_back((long long)(nums[i] ^ k) - nums[i]);
        }
        
        sort(gains.begin(), gains.end(), greater<long long>());
        
        long long maxGain = 0;
        long long currentGain = 0;
        
        for (int i = 0; i < n; i++) {
            currentGain += gains[i];
            if (i % 2 == 1) {  // 偶数个节点
                maxGain = max(maxGain, currentGain);
            }
        }
        
        return totalSum + maxGain;
    }
};

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        gains = []
        total_sum = 0
        
        for num in nums:
            total_sum += num
            gains.append((num ^ k) - num)
        
        gains.sort(reverse=True)
        
        max_gain = 0
        current_gain = 0
        
        for i, gain in enumerate(gains):
            current_gain += gain
            if i % 2 == 1:  # 偶数个节点
                max_gain = max(max_gain, current_gain)
        
        return total_sum + max_gain

public class Solution {
    public long MaximumValueSum(int[] nums, int k, int[][] edges) {
        int n = nums.Length;
        long[] gains = new long[n];
        long totalSum = 0;
        
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
            gains[i] = (long)(nums[i] ^ k) - nums[i];
        }
        
        Array.Sort(gains, (a, b) => b.CompareTo(a));
        
        long maxGain = 0;
        long currentGain = 0;
        
        for (int i = 0; i < n; i++) {
            currentGain += gains[i];
            if (i % 2 == 1) {  // 偶数个节点
                maxGain = Math.Max(maxGain, currentGain);
            }
        }
        
        return totalSum + maxGain;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number[][]} edges
 * @return {number}
 */
var maximumValueSum = function(nums, k, edges) {
    let n = nums.length;
    let deltas = [];
    let sum = 0;
    
    for (let i = 0; i < n; i++) {
        sum += nums[i];
        deltas.push((nums[i] ^ k) - nums[i]);
    }
    
    deltas.sort((a, b) => b - a);
    
    let maxSum = sum;
    let currentSum = sum;
    
    for (let i = 1; i < n; i += 2) {
        currentSum += deltas[i-1] + deltas[i];
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	时间复杂度	空间复杂度
贪心算法	O(n log n)	O(n)

时间复杂度：O(n log n)，主要消耗在排序操作上空间复杂度：O(n)，需要额外数组存储增益值

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目