这是一道非常经典的结合了图论性质与贪心算法的题目。以下是详细的思路解析与 Java 代码实现。
核心思路分析
1. 挖掘树的隐藏性质（脑筋急转弯）：
题目规定每次操作必须选择一条边，将相连的两个节点同时异或 k。但深入思考会发现，树中任意两个节点之间都存在唯一一条路径。如果我们对这条路径上的所有边都进行一次异或操作，最终的结果是：只有路径两端的节点被异或了一次 k，而路径中间的所有节点都被异或了两次（根据异或性质 x ^ k ^ k = x，中间节点的值保持不变）。
由此得出关键结论：我们可以任选任意两个节点，使它们的值同时异或一次 k。因此，题目中的 edges 数组实际上是一个干扰项，我们可以完全忽略它。
2. 转化为差值最大化问题：
既然可以任选两个节点进行异或，且每次操作必须涉及两个节点，问题就转化为了：如何分组配对，使得异或后的节点总价值尽可能大？
– 异或操作是可逆的，因此每个节点最多只需要考虑异或一次。
– 我们可以计算每个节点如果进行一次异或操作后的“收益”：diff[i] = (nums[i] ^ k) – nums[i]。
3. 贪心策略：
– 首先计算所有节点不进行任何操作时的原始总价值。
– 计算每个节点的收益 diff[i]，并将其按降序排序。
– 因为每次操作必须成对进行，所以我们每次从排序后的数组中取出最大的两个收益值相加。如果它们的和大于等于 0，说明这一对操作能带来正向收益，将其加入总价值；如果和小于 0，则停止操作，因为后续的收益只会更小。
Java 代码实现
import java.util.Arrays;
class Solution {
public long maximumValueSum(int[] nums, int k, int[][] edges) {
long ans = 0;
int n = nums.length;
int[] diff = new int[n];
// 1. 计算原始总价值，并求出每个节点异或 k 后的收益差值
for (int i = 0; i < n; i++) {
ans += nums[i];
diff[i] = (nums[i] ^ k) – nums[i];
}
// 2. 将收益差值按升序排序
Arrays.sort(diff);
// 3. 贪心配对：从最大的两个差值开始尝试配对
// 只要两个差值之和 >= 0，就执行异或操作（累加收益）
for (int i = n – 1; i > 0 && diff[i] + diff[i – 1] >= 0; i -= 2) {
ans += diff[i] + diff[i – 1];
}
return ans;
}
}
复杂度分析
– 时间复杂度：O(n log n)。其中 n 是节点数，主要耗时在对 diff 数组进行排序，后续的遍历操作仅需 O(n) 的时间。
– 空间复杂度：O(n)。主要用于存储 diff 差值数组。
