What is the main trick in Find the Maximum Sum of Node Values?

The main trick is proving that the tree operations are equivalent to choosing an even number of nodes to apply XOR with k. Once you convert each node into a gain value, the problem becomes maximizing total gain under even parity.

Why can I ignore the exact tree shape?

Because on a tree, combining edge operations along paths lets you toggle endpoints while intermediate effects cancel in pairs. The result is that any even-sized set of nodes is achievable, so the structure matters only for that feasibility fact.

Is this really a binary-tree traversal and state tracking problem?

It can be framed that way if you root the tree and reason about parity states, but the optimal implementation does not need an actual traversal. The important state is even versus odd count of chosen XOR gains, which collapses the tree into a two-state optimization.

Why does taking all positive gains sometimes give the wrong answer?

Because the number of chosen positive-gain nodes might be odd, and an odd number of toggled nodes cannot be produced by operations that always affect two endpoints. You must repair parity by sacrificing the smallest positive gain or accepting the least harmful non-positive gain.

What are the best time and space bounds for LeetCode 3068?

You can solve it in O(n) time and O(1) extra space. Each node contributes one gain calculation, and you only need running totals plus the best parity adjustment values.

#3068

Hard

auto_awesome二分·树·traversal

LeetCode 题解工作台

最大节点价值之和

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

数组动态规划贪心位运算树

题目描述

给你一棵 n 个节点的无向树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [u_i, v_i] 表示树中节点 u_i 和 v_i 之间有一条边。同时给你一个正整数 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 * 10⁴
1 <= k <= 10⁹
0 <= nums[i] <= 10⁹
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
输入保证 edges 构成一棵合法的树。

lightbulb

解题思路

方法一：动态规划

对于任意一个数 $x$ ，与 $k$ 异或偶数次后，值不变。所以，对于一棵树的任意一条路径，我们将路径上所有的边都进行操作，那么该路径上除了起点和终点外，其他节点的值都不会改变。

另外，无论进行了多少次操作，总会有偶数个元素异或了 $k$ ，其余元素不变。

因此，问题转化为：对于数组 $\textit{nums}$ ，任选其中偶数个元素异或 $k$ ，使得和最大。

我们可以使用动态规划解决这个问题。设 $f_0$ 表示当前有偶数个元素异或了 $k$ 时的最大和，而 $f_1$ 表示当前有奇数个元素异或了 $k$ 时的最大和。那么状态转移方程为：

\begin{aligned} f_0 &= \max(f_0 + x, f_1 + (x \oplus k)) \\ f_1 &= \max(f_1 + x, f_0 + (x \oplus k)) \end{aligned}

其中 $x$ 表示当前元素的值。

我们遍历数组 $\textit{nums}$ ，根据上述状态转移方程更新 $f_0$ 和 $f_1$ ，最后返回 $f_0$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        f0, f1 = 0, -inf
        for x in nums:
            f0, f1 = max(f0 + x, f1 + (x ^ k)), max(f1 + x, f0 + (x ^ k))
        return f0

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
They want you to notice that edge operations do not require tree DP over children; the tree only enforces even toggle parity.
question_mark
A strong solution quickly rewrites the problem from modifying edges to selecting node-wise XOR gains under an even-count constraint.
question_mark
If you mention rooting the tree, the useful conclusion is feasibility of any even-sized toggled set, not a full binary-tree recurrence.

warning

常见陷阱

外企场景

error
Greedily taking every node where nums[i] XOR k is larger than nums[i] without checking whether that chosen count is odd.
error
Building a full traversal-based DP on the tree and overcomplicating a problem whose final state depends only on parity of toggled nodes.
error
Assuming the exact edge sequence matters for the maximum sum, when only the reachable even-cardinality set of changed nodes matters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual set of nodes to toggle instead of only the maximum sum, which requires reconstructing the parity choice.
arrow_right_alt
Replace the tree with a general connected graph; the same even-parity reachability idea still drives the optimization.
arrow_right_alt
Ask for the maximum sum after exactly m operations, which changes the simple parity view into a tighter operation-count constraint.

help

常见问题

外企场景

继续练习

#2708 一个小组的最大实力值 #2673 使二叉树所有路径值相等的最小代价 #3035 回文字符串的最大数量