LeetCode 3068.最大节点价值之和：脑筋急转弯+动态规划（O(1)空间）

【LetMeFly】3068.最大节点价值之和：脑筋急转弯+动态规划（O(1)空间）

力扣题目链接：https://leetcode.cn/problems/find-the-maximum-sum-of-node-values/

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

Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：

• 选择连接节点 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解释：Alice 不需要执行任何操作，就可以得到最大价值之和 42 。

提示：

• 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
• 输入保证 edges 构成一棵合法的树。

挺有意思的题

解题方法：动态规划

推导一

前提：

1. 一个数异或$k$两次相当于没异或
2. 选择树中一条路径上的所有边，相当于只有路径两端的两个元素异或了$k$（中间每个元素都会异或$k$两次）
3. 树上任意两点之间存在一条路径

结论：

1. 相当于我可以从$nums$数组中任选两个数异或，实际上我连边都有哪些都不用管，edges数组直接删！

推导二

前提：

1. 每次操作都会作用两个数

   1. 如果操作前两个数都异或过，操作后相当于两个数都没异或过
   2. 如果操作前两个数都没异或过，操作后相当于两个数都异或过
   3. 如果操作前两个数一个异或过一个没异或过，操作后相当于两个数一个没异或过一个异过

结论：

1. 无论操作多少次，都相当于有偶数个数被异或了

解题思路

我们可以使用动态规划数组$odd[i]$代表$nums$前$i$个数中有奇数个被异或过的元素最大和，$even[i]$代表$nums$前$i$个数中有偶数个被异或过的元素最大和。

对于一个数$nums[i]$，可以选择也可以不选，对应

$odd[i]=\max (odd[i]+nums[i],even[i]+(nums[i]\text{^}k))$

$even[i]=\max (even[i]+nums[i],odd[i]+(nums[i]\text{^}k))$

当然也可以原地滚动优化空间。

时空复杂度分析

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/* * @Author: LetMeFly * @Date: 2025-05-27 23:28:05 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-05-27 23:34:08 */typedef long long ll;class Solution {public: ll maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) { ll odd = LLONG_MIN, even = 0; for (int t : nums) { ll newO = max(odd + t, even + (t ^ k)); ll newE = max(even + t, odd + (t ^ k)); odd = newO, even = newE; } return even; }};

Python

\'\'\'Author: LetMeFlyDate: 2025-05-27 23:28:05LastEditors: LetMeFly.xyzLastEditTime: 2025-05-27 23:40:11\'\'\'from typing import Listclass Solution: def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int: odd, even = -100000000000000, 0 for t in nums: odd, even = max(odd + t, even + (t ^ k)), max(even + t, odd + (t ^ k)) return even

Java

/* * @Author: LetMeFly * @Date: 2025-05-27 23:28:05 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-05-27 23:45:06 */class Solution { public long maximumValueSum(int[] nums, int k, int[][] edges) { long even = 0, odd = -1000000000000000L; // 记得带“L” for (int t : nums) { long newO = Math.max(odd + t, even + (t ^ k)); long newE = Math.max(even + t, odd + (t ^ k)); odd = newO; even = newE; } return even; }}

Go

/* * @Author: LetMeFly * @Date: 2025-05-27 23:28:05 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-05-27 23:49:20 */package mainfunc maximumValueSum(nums []int, k int, edges [][]int) int64 { odd, even := int64(-10000000000000000), int64(0) // -1...0也可能是int for _, t := range nums { odd, even = max(odd + int64(t), even + int64(t ^ k)), max(even + int64(t), odd + int64(t ^ k)) } return even}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源