LeetCode 题解工作台
从树中删除边的最小分数
存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点， 以及 n - 1 条边。 给你一个下标从 0 开始的整数数组 nums ，长度为 n ，其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [a …
4
题型
7
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
我们记树的异或和为 ，即 $s = \text{nums}[0] \oplus \text{nums}[1] \oplus \ldots \oplus \text{nums}[n-1]$。 接下来，枚举 的每个点 作为树的根节点，将根节点与某个子节点 相连的边作为第一条被删除的边。这样我们就获得了两个连通块，我们记包含根节点 的连通块的异或和为 ，然后我们对包含根节点 的连通块进行 DF…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点， 以及 n - 1 条边。
给你一个下标从 0 开始的整数数组 nums ，长度为 n ，其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边。
删除树中两条 不同 的边以形成三个连通组件。对于一种删除边方案，定义如下步骤以计算其分数：
- 分别获取三个组件 每个 组件中所有节点值的异或值。
- 最大 异或值和 最小 异或值的 差值 就是这一种删除边方案的分数。
- 例如，三个组件的节点值分别是：
[4,5,7]、[1,9]和[3,3,3]。三个异或值分别是4 ^ 5 ^ 7 = 6、1 ^ 9 = 8和3 ^ 3 ^ 3 = 3。最大异或值是8，最小异或值是3，分数是8 - 3 = 5。
返回在给定树上执行任意删除边方案可能的 最小 分数。
示例 1：
输入：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]] 输出：9 解释：上图展示了一种删除边方案。 - 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。 - 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。 - 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。 分数是最大异或值和最小异或值的差值，10 - 1 = 9 。 可以证明不存在分数比 9 小的删除边方案。
示例 2：
输入：nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]] 输出：0 解释：上图展示了一种删除边方案。 - 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。 - 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。 - 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。 分数是最大异或值和最小异或值的差值，0 - 0 = 0 。 无法获得比 0 更小的分数 0 。
提示：
n == nums.length3 <= n <= 10001 <= nums[i] <= 108edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges表示一棵有效的树
解题思路
方法一：DFS + 子树异或和
我们记树的异或和为 ，即 。
接下来，枚举 的每个点 作为树的根节点，将根节点与某个子节点 相连的边作为第一条被删除的边。这样我们就获得了两个连通块，我们记包含根节点 的连通块的异或和为 ，然后我们对包含根节点 的连通块进行 DFS，计算出每个子树的异或和，记每次 DFS 计算出的子树异或和为 。那么三个连通块的异或和分别为 , 和 。我们需要计算这三个异或和的最大值和最小值，记为 和 ，那么对于枚举的每一种情况，得到的分数为 。求所有情况的最小值作为答案。
计算每个子树的异或和可以通过 DFS 实现。定义一个函数 ，表示从节点 开始 DFS，而 是节点 的父节点。函数返回值为以节点 为根的子树的异或和。
时间复杂度 ，空间复杂度 。其中 是树的节点数。
class Solution:
def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
def dfs(i: int, fa: int) -> int:
res = nums[i]
for j in g[i]:
if j != fa:
res ^= dfs(j, i)
return res
def dfs2(i: int, fa: int) -> int:
nonlocal s, s1, ans
res = nums[i]
for j in g[i]:
if j != fa:
s2 = dfs2(j, i)
res ^= s2
mx = max(s ^ s1, s2, s1 ^ s2)
mn = min(s ^ s1, s2, s1 ^ s2)
ans = min(ans, mx - mn)
return res
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
s = reduce(lambda x, y: x ^ y, nums)
n = len(nums)
ans = inf
for i in range(n):
for j in g[i]:
s1 = dfs(i, j)
dfs2(i, j)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) due to evaluating each pair of edges for removal and computing the XOR differences using precomputed subtree values. Space complexity is O(n) to store the XOR of each subtree and track visited nodes during DFS. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for a solution using binary-tree traversal and subtree state tracking.
- question_mark
Expect handling of XOR aggregation efficiently to avoid recalculation for each edge pair.
- question_mark
Check that the candidate properly identifies overlapping subtrees when removing edges.
常见陷阱
外企场景- error
Failing to precompute subtree XORs and recalculating for every edge pair.
- error
Double-counting nodes when the two removed edges affect nested subtrees.
- error
Ignoring edge cases where one component might contain only a single node.
进阶变体
外企场景- arrow_right_alt
Instead of XOR, compute sum differences among components after edge removals.
- arrow_right_alt
Apply the problem to a weighted tree where edge weights influence component value.
- arrow_right_alt
Generalize to removing k edges to create k+1 components with minimal XOR score.