NeetCode #826LC-3068HardGreedy
← Back to All Problems#826 · #3068 · Find the Maximum Sum of Node Values(最大节点价值之和)
📌 Problem Statement & Constraints
You are given a tree with
n nodes, an array nums of node values, an integer k, and edges describing the tree. In one operation, choose an edge and replace both endpoint values with their XOR by k. Maximise the sum of all node values. Constraints: 2 <= n <= 2 * 10^4, 1 <= nums[i], k <= 10^9.💡 Core Algorithmic Approaches
- An operation flips the parity of two adjacent nodes, so the achievable sets of flipped nodes are exactly the subsets of even size (a tree is connected).
- Define
gain[i] = (nums[i] XOR k) - nums[i]; flipping a node changes the total by its gain. - Take every positive gain; if their count is even, that set is achievable and the total is optimal.
- If the count is odd, the parity must change by one, so subtract the smallest absolute gain over all nodes (dropping a small positive, or adding a small negative).
💻 Benchmark Python3 Implementation
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
base = sum(nums)
gains = [(v ^ k) - v for v in nums]
positive = [g for g in gains if g > 0]
total = base + sum(positive)
if len(positive) % 2 == 0:
return total
# odd count -> fix the parity by sacrificing the cheapest single gain
return total - min(abs(g) for g in gains)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to build gains and one to fold them.
💾 Space Complexity
O(n): the gains list.
⚠️ Interview Pitfalls & Follow-ups
- Ignoring the parity constraint: each operation flips exactly two nodes, so an even-sized set is all that is achievable; an odd set is not.
- Only considering positive gains when fixing parity: the cheapest fix may be adding a small negative gain (flipping one more node), which is why the minimum is over
absof all gains. - Using the edges to build the tree: the edges only certify connectivity; the tree structure is irrelevant to the parity argument.
- Assuming
kis small:kcan be up to 10^9, so the XOR can turn a large value into a small one or vice versa -- the sign of the gain is what matters.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.