LeetCode 题解工作台
创建价值相同的连通块
有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。 给你一个长度为 n 下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 个节点的值。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示节点 a …
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
假设连通块的个数为 ，那么要删除的边数为 ，每个连通块的价值为 ，其中 为 所有节点的值之和。 我们从大到小枚举 ，如果存在一个 ，使得 是整数，并且得到的每个连通块的价值都相等，那么直接返回 。其中 的初始值为 $\min(n, \frac{s}{mx})$，记 为 中的最大值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。
给你一个长度为 n 下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 个节点的值。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 与 bi 之间有一条边。
你可以 删除 一些边，将这棵树分成几个连通块。一个连通块的 价值 定义为这个连通块中 所有 节点 i 对应的 nums[i] 之和。
你需要删除一些边，删除后得到的各个连通块的价值都相等。请返回你可以删除的边数 最多 为多少。
示例 1：
输入：nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] 输出：2 解释：上图展示了我们可以删除边 [0,1] 和 [3,4] 。得到的连通块为 [0] ，[1,2,3] 和 [4] 。每个连通块的价值都为 6 。可以证明没有别的更好的删除方案存在了，所以答案为 2 。
示例 2：
输入：nums = [2], edges = [] 输出：0 解释：没有任何边可以删除。
提示：
1 <= n <= 2 * 104nums.length == n1 <= nums[i] <= 50edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edges表示一棵合法的树。
解题思路
方法一：枚举连通块的个数
假设连通块的个数为 ，那么要删除的边数为 ，每个连通块的价值为 ，其中 为 所有节点的值之和。
我们从大到小枚举 ，如果存在一个 ，使得 是整数，并且得到的每个连通块的价值都相等，那么直接返回 。其中 的初始值为 ，记 为 中的最大值。
关键点在于判断对于给定的 ，是否能划分出若干子树，使得每棵子树的价值都为 。
这里我们通过 dfs 函数来判断，从上到下递归遍历求出各个子树的价值，如果子树价值和恰好为 ，说明此时划分成功，我们将价值置为 返回给上一层，表示此子树可以与父节点断开。如果子树价值之和大于 ，说明此时划分失败，我们返回 ，表示无法划分。
时间复杂度 ，其中 和 分别为 的长度和 所有节点的值之和。
class Solution:
def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
def dfs(i, fa):
x = nums[i]
for j in g[i]:
if j != fa:
y = dfs(j, i)
if y == -1:
return -1
x += y
if x > t:
return -1
return x if x < t else 0
n = len(nums)
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
s = sum(nums)
mx = max(nums)
for k in range(min(n, s // mx), 1, -1):
if s % k == 0:
t = s // k
if dfs(0, -1) == 0:
return k - 1
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of divisors of the total sum multiplied by DFS traversal of n nodes, giving O(n * number_of_divisors). Space complexity is O(n) for recursion stack and tracking subtree sums. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify the divisor-based approach early.
- question_mark
Look for correct DFS implementation that handles subtree sum tracking.
- question_mark
Check reasoning about maximum edge deletions and component count.
常见陷阱
外企场景- error
Failing to consider all divisors of the total sum and missing valid partitions.
- error
Incorrectly handling DFS so that subtree sums are miscounted.
- error
Assuming components can have unequal sums or miscounting edge deletions.
进阶变体
外企场景- arrow_right_alt
Consider weighted nodes with larger ranges requiring careful divisor enumeration.
- arrow_right_alt
Use a similar approach to split a forest into equal-sum components instead of a single tree.
- arrow_right_alt
Modify to find minimum edges to delete to achieve exactly k equal-sum components.