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] ,并将它们的值更新为:
    <ul>
    	<li><code>nums[u] = nums[u] XOR k</code></li>
    	<li><code>nums[v] = nums[v] XOR k</code></li>
    </ul>
    </li>
    

请你返回 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]\verb|^|k))$

$even[i]=\max(even[i]+nums[i], odd[i]+(nums[i]\verb|^|k))$

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

时空复杂度分析

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

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* @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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
'''
Author: LetMeFly
Date: 2025-05-27 23:28:05
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-27 23:40:11
'''
from typing import List

class 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* @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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* @Author: LetMeFly
* @Date: 2025-05-27 23:28:05
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-05-27 23:49:20
*/
package main

func 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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


3068.最大节点价值之和:脑筋急转弯+动态规划(O(1)空间)
https://blog.letmefly.xyz/2025/05/27/LeetCode 3068.最大节点价值之和/
作者
发布于
2025年5月27日
许可协议