题目链接

3068. 最大节点价值之和 - 力扣（LeetCode）

题目描述

给你一棵n个节点的 无向 树，节点从0到n - 1编号。树以长度为n - 1下标从 0 开始的二维整数数组edges的形式给你，其中edges[i] = [ui, vi]表示树中节点ui和vi之间有一条边。同时给你一个 正 整数k和一个长度为n下标从 0 开始的 非负 整数数组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 是可以得到最大的价值之和。

解题思路

1. 问题描述：
   • 给定一棵树（无向无环图），每个节点有一个整数值nums[i]。
   • 可以对任意数量的节点进行异或操作：nums[i] ^= k。
   • 目标是最大化整棵树的节点值之和。
2. 关键观察：
   • 异或操作是可逆的：对一个节点异或两次等于没有异或。
   • 最优解中，每个节点最多被异或一次。
   • 需要动态规划来记录每个节点是否被异或的最优解。
3. 算法选择：
   • 使用树形动态规划（DFS + DP）。
   • 对每个节点维护两个状态：
     • f0: 该节点未被异或时的子树最大和。
     • f1: 该节点被异或后的子树最大和。
   • 通过DFS遍历树，从叶子节点向上递推每个节点的f0和f1。
4. 动态转移：
   • 对于当前节点x，遍历其所有子节点y。
   • 更新f0和f1：
     • f0可以是x未被异或 + 子节点y未被异或，或x未被异或 + 子节点y被异或。
     • f1可以是x被异或 + 子节点y未被异或，或x被异或 + 子节点y被异或。
   • 最终结果是max(f0, f1)。

题解代码

classSolution{publiclongmaximumValueSum(int[]nums,intk,int[][]edges){intn=nums.length;// 构建邻接表表示的树结构List<Integer>[]g=newArrayList[n];Arrays.setAll(g,i->newArrayList<>());for(int[]e:edges){intx=e[0];inty=e[1];g[x].add(y);g[y].add(x);}// 从根节点0开始DFS，初始父节点为-1（表示无父节点）returndfs(0,-1,g,nums,k)[0];}privatelong[]dfs(intx,intfa,List<Integer>[]g,int[]nums,intk){// f0: 当前节点x未被异或时的最大值// f1: 当前节点x被异或后的最大值longf0=0;longf1=Long.MIN_VALUE;// 初始设为极小值，表示不可能的情况// 遍历所有子节点for(inty:g[x]){if(y!=fa){// 避免回到父节点// 递归处理子节点ylong[]r=dfs(y,x,g,nums,k);// 动态更新f0和f1:// t 表示当前节点x被异或的情况下，子节点y是否被异或的最优解longt=Math.max(f1+r[0],f0+r[1]);// 更新f0: 当前节点x未被异或的情况下，子节点y是否被异或的最优解f0=Math.max(f0+r[0],f1+r[1]);f1=t;}}// 返回结果:// [0]: 当前子树的最大和（x未被异或或x被异或）// [1]: 当前子树的最大和（x未被异或或x被异或）returnnewlong[]{Math.max(f0+nums[x],f1+(nums[x]^k)),Math.max(f1+nums[x],f0+(nums[x]^k))};}}

复杂度分析

1. 时间复杂度：
   • DFS遍历整棵树，每个节点被访问一次。
   • 对于每个节点，处理其所有子节点（树中边数为n-1，所以总操作数为O(n)）。
   • 总时间复杂度：O(n)。
2. 空间复杂度：
   • 邻接表存储树结构：O(n)。
   • DFS递归栈深度：最坏情况下为树的高度，平均O(log n)（平衡树），最坏O(n)（链状树）。
   • 总空间复杂度：O(n)。