题目链接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 knums[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 是可以得到最大的价值之和。解题思路问题描述给定一棵树无向无环图每个节点有一个整数值nums[i]。可以对任意数量的节点进行异或操作nums[i] ^ k。目标是最大化整棵树的节点值之和。关键观察异或操作是可逆的对一个节点异或两次等于没有异或。最优解中每个节点最多被异或一次。需要动态规划来记录每个节点是否被异或的最优解。算法选择使用树形动态规划DFS DP。对每个节点维护两个状态f0: 该节点未被异或时的子树最大和。f1: 该节点被异或后的子树最大和。通过DFS遍历树从叶子节点向上递推每个节点的f0和f1。动态转移对于当前节点x遍历其所有子节点y。更新f0和f1f0可以是x未被异或 子节点y未被异或或x未被异或 子节点y被异或。f1可以是x被异或 子节点y未被异或或x被异或 子节点y被异或。最终结果是max(f0, f1)。题解代码classSolution{publiclongmaximumValueSum(int[]nums,intk,int[][]edges){intnnums.length;// 构建邻接表表示的树结构ListInteger[]gnewArrayList[n];Arrays.setAll(g,i-newArrayList());for(int[]e:edges){intxe[0];intye[1];g[x].add(y);g[y].add(x);}// 从根节点0开始DFS初始父节点为-1表示无父节点returndfs(0,-1,g,nums,k)[0];}privatelong[]dfs(intx,intfa,ListInteger[]g,int[]nums,intk){// f0: 当前节点x未被异或时的最大值// f1: 当前节点x被异或后的最大值longf00;longf1Long.MIN_VALUE;// 初始设为极小值表示不可能的情况// 遍历所有子节点for(inty:g[x]){if(y!fa){// 避免回到父节点// 递归处理子节点ylong[]rdfs(y,x,g,nums,k);// 动态更新f0和f1:// t 表示当前节点x被异或的情况下子节点y是否被异或的最优解longtMath.max(f1r[0],f0r[1]);// 更新f0: 当前节点x未被异或的情况下子节点y是否被异或的最优解f0Math.max(f0r[0],f1r[1]);f1t;}}// 返回结果:// [0]: 当前子树的最大和x未被异或或x被异或// [1]: 当前子树的最大和x未被异或或x被异或returnnewlong[]{Math.max(f0nums[x],f1(nums[x]^k)),Math.max(f1nums[x],f0(nums[x]^k))};}}复杂度分析时间复杂度DFS遍历整棵树每个节点被访问一次。对于每个节点处理其所有子节点树中边数为n-1所以总操作数为O(n)。总时间复杂度O(n)。空间复杂度邻接表存储树结构O(n)。DFS递归栈深度最坏情况下为树的高度平均O(log n)平衡树最坏O(n)链状树。总空间复杂度O(n)。