LeetCode 题解工作台
可以被 K 整除连通块的最大数目
给你一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示树中节点 a i 和 b i 有一条边。 同时给你一个下标从 0 开始长度为 n 的整数数组 values …
2
题型
6
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
我们注意到，题目保证了整棵树的节点值之和可以被 整除，因此，如果我们删除一棵元素和能被 整除的子树，那么剩下的每个连通块的节点值之和也一定可以被 整除。 因此，我们可以使用深度优先搜索的方法，从根节点开始遍历整棵树，对于每个节点，我们计算其子树中所有节点值之和，如果该和能被 整除，那么我们就将答案加一。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。
同时给你一个下标从 0 开始长度为 n 的整数数组 values ，其中 values[i] 是第 i 个节点的 值 。再给你一个整数 k 。
你可以从树中删除一些边，也可以一条边也不删，得到若干连通块。一个 连通块的值 定义为连通块中所有节点值之和。如果所有连通块的值都可以被 k 整除，那么我们说这是一个 合法分割 。
请你返回所有合法分割中，连通块数目的最大值 。
示例 1：
输入：n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6 输出：2 解释：我们删除节点 1 和 2 之间的边。这是一个合法分割，因为： - 节点 1 和 3 所在连通块的值为 values[1] + values[3] = 12 。 - 节点 0 ，2 和 4 所在连通块的值为 values[0] + values[2] + values[4] = 6 。 最多可以得到 2 个连通块的合法分割。
示例 2：
输入：n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3 输出：3 解释：我们删除节点 0 和 2 ，以及节点 0 和 1 之间的边。这是一个合法分割，因为： - 节点 0 的连通块的值为 values[0] = 3 。 - 节点 2 ，5 和 6 所在连通块的值为 values[2] + values[5] + values[6] = 9 。 - 节点 1 ，3 和 4 的连通块的值为 values[1] + values[3] + values[4] = 6 。 最多可以得到 3 个连通块的合法分割。
提示：
1 <= n <= 3 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nvalues.length == n0 <= values[i] <= 1091 <= k <= 109values之和可以被k整除。- 输入保证
edges是一棵无向树。
解题思路
方法一：DFS
我们注意到，题目保证了整棵树的节点值之和可以被 整除，因此，如果我们删除一棵元素和能被 整除的子树，那么剩下的每个连通块的节点值之和也一定可以被 整除。
因此，我们可以使用深度优先搜索的方法，从根节点开始遍历整棵树，对于每个节点，我们计算其子树中所有节点值之和，如果该和能被 整除，那么我们就将答案加一。
时间复杂度 ，空间复杂度 。其中 是树中的节点数。
class Solution:
def maxKDivisibleComponents(
self, n: int, edges: List[List[int]], values: List[int], k: int
) -> int:
def dfs(i: int, fa: int) -> int:
s = values[i]
for j in g[i]:
if j != fa:
s += dfs(j, i)
nonlocal ans
ans += s % k == 0
return s
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
ans = 0
dfs(0, -1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Check whether the sum of values in subtrees is divisible by k after each DFS call.
- question_mark
Consider edge removal only when a subtree sum modulo k equals zero to maximize component count.
- question_mark
Be mindful of tree rooting and parent-child relationships to avoid revisiting nodes.
常见陷阱
外企场景- error
Failing to propagate the correct modulo k sum from child to parent, causing undercounting components.
- error
Counting a subtree as a component before verifying its sum modulo k equals zero.
- error
Ignoring the necessity of rooting the tree to track parent-child relationships correctly during DFS.
进阶变体
外企场景- arrow_right_alt
Modify the problem to find the maximum number of components divisible by a variable k for multiple queries.
- arrow_right_alt
Allow negative node values and adjust DFS aggregation to handle negative modulo correctly.
- arrow_right_alt
Compute minimum number of edges to remove instead of maximum components, which changes DFS decision logic.