【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]\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: LetMeFly
Date: 2025-05-27 23:28:05
LastEditors: LetMeFly.xyz
LastEditTime: 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, 0for 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也可能是intfor _, t := range nums {odd, even = max(odd + int64(t), even + int64(t ^ k)), max(even + int64(t), odd + int64(t ^ k))}return even
}

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源