LeetCode 2872「最大化 K 整除连通块数目」：倍数封闭性引理与单次 DFS 题解（codeforces-go 仓库 Go 实现解析）

• 科学计算

导读

本文围绕 LeetCode 2872「最大化 K 整除连通块数目」展开，完整还原官方题解的数学推导：从"倍数对加法封闭"这条数论性质出发，证明一条边可被删除的充要条件，并把"最大化连通块数目"转化为"尽可能多删除边"的贪心问题。文章给出 Python3 / Java / C++ / Go / JavaScript / Rust 六种语言的实现，并对照本仓库 leetcode/biweekly/114/d/d.go 中的 Go 解法、d_test.go 测试驱动方式与测试用例文件 d.txt，让读者既吃透算法本质，又能直接在本仓库中复现、运行与扩展验证。读完本文，你将掌握一类"树 + 整除约束"问题的通法：DFS 自底向上计算子树点权和，并利用取模统计答案。

题目背景与问题转化

给定一棵包含n个节点的无向树，每个节点带有一个非负整数权值values[i]，另给定整数k。要求删除若干条边，使得删除后每个连通块的节点权值之和都能被k整除，问最多能得到多少个这样的连通块。题目保证整棵树的权值总和是k的倍数。

问题转化的第一步至关重要：最大化连通块的数目，等价于最大化删除的边数加一。设删除边数为e，每删除一条边，连通块数量恰好增加 1（树是无环图，删除任意一条边不会改变其他连通块内部结构），因此最终连通块数 =e + 1。于是"求最多连通块数"变成了"求最多可删边数"。

这一转化把目标从"构造划分"降维为"逐边判定"，而逐边判定又可以交给 DFS 自底向上一次性完成，这正是本文算法的核心杠杆。

数学引理：k 的倍数对加法封闭

在动手删边之前，先回答一个根本问题：什么样的边可以删除？题解给出了一个非常优美的数论观察：

如果x和y都是k的倍数，那么x + y也是k的倍数。

例如k = 3时，3和6都是3的倍数，则3 + 6 = 9同样是3的倍数。这是整除理论中"倍数集对加法封闭"的直接体现，也是整个解法的基石。

取其逆否命题：

如果x + y不是k的倍数，那么x和y不全是k的倍数。

进一步延伸：一个不是k的倍数的数，无论怎样拆分成若干个加数之和，拆分出的加数中始终至少存在一个不是k的倍数的数（否则由封闭性，总和就应当是k的倍数，矛盾）。

这条引理把"整体不可整除"的判定转化为"局部必然存在不可整除子块"的必然性结论，为后续"边能否删除只看切分后两个块各自的点权和"提供了理论支撑。

什么样的边可以删除：充要条件

把上述引理搬到树上。删除一条边后，一个连通块被分成两个连通块。题解的核心论断是：

当且仅当切分出来的两个连通块的点权和都是k的倍数，这条边才能删除。

必要性

如果删边后两个连通块点权和都满足整除条件，则删除后的划分显然是合法的（每个块都是k的倍数），此时可以删。

充分性

反过来，如果其中一个连通块的点权和不是k的倍数，那么由引理可知：无论这个块内部再如何分割，始终会存在一个点权和不是k的倍数的连通块。也就是说，一旦某条边把树切成一个"总和不可整除"的块，这个块就永远无法被合法地消化掉，整棵树的划分合法性就被破坏。因此这样的边不能删。

这个"不可整除块会像瑕疵一样永远存在"的结论，直接决定了全局贪心的正确性，是全文最关键的证明环节。

由可删性到贪心

由于删除一条"可删边"后，切出的两个块点权和都仍是k的倍数，它们各自内部仍然保持"整棵树是k的倍数"这一前提不变，因此可以继续在新块内部寻找可删边。反复执行：

只要有能删除的边，就删除。

每一步删除都让连通块数目 +1 且不破坏合法性，最终得到的就是最优解。这与经典贪心"能切就切"的直觉一致，而其正确性正是建立在上述充要条件之上：错过一条可删边不会带来任何收益，反而损失一块连通块。

如何找到可删除的边：DFS 后序遍历

删一条边会把树分成两个连通块。由于题目保证整棵树的点权和是k的倍数，因此判断一条边是否可删时，只需检查其中一个连通块的点权和是否为k的倍数（另一个块自动满足：总和 − 已检查块，仍为k的倍数）。

这带来一个极具工程便利性的简化：我们不必同时计算两个块，只要从任意一点（如 0 号节点）出发做一次 DFS，自底向上计算子树x的点权和s：

• 若某个子树x的点权和s是k的倍数，则说明"子树x"这一块可被切下，x到其父节点的这条边可以删除（x为根节点时没有父节点，特殊处理）；
• 统计所有满足条件的s，即为可删边数。

根节点的巧妙处理

注意到根节点没有父节点，"根到父节点的边"并不存在。但我们可以把这条不存在的边也视作可计数：因为整棵树总和是k的倍数，根节点自身必然贡献一次s % k == 0的计数。这样：

连通块的数目 = 删除的边数 + 1 = 统计到的满足整除条件的子树个数。

即 DFS 过程中每个"点权和为k的倍数"的子树都对应一个连通块，答案直接在递归过程中累加，无需再单独加 1。这是本解法最精妙、也最容易被忽略的细节：ans的初始值取 0，整个 DFS 结束后直接返回ans即可。

递归过程示意

以dfs(x, fa)表示"返回以x为根的子树点权和"：

1. 初始化s = values[x]（包含节点自身的权值）；
2. 遍历x的所有邻居y，跳过y == fa（避免走回父节点形成环）；
3. 递归累加s += dfs(y, x)，得到子树点权和；
4. 判断s % k == 0，成立则ans++；
5. 返回s给父层使用。

由于是后序（自底向上）累加，每个节点恰好被访问一次，总复杂度为线性。

六种语言实现

题解为同一算法提供了六种主流语言的实现，下面逐一完整给出。它们逻辑完全一致，仅语法不同：

Python3

class Solution: def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int: g = [[] for _ in range(n)] for x, y in edges: g[x].append(y) g[y].append(x) # 返回子树 x 的点权和 def dfs(x: int, fa: int) -> int: s = values[x] for y in g[x]: if y != fa: # 避免访问父节点 # 加上子树 y 的点权和，得到子树 x 的点权和 s += dfs(y, x) nonlocal ans ans += s % k == 0 return s ans = 0 dfs(0, -1) return ans

Python 版本利用nonlocal ans在嵌套函数中直接修改外层计数，ans += s % k == 0将布尔值隐式转为 0/1 累加，代码极简。

Java

class Solution { private int ans; public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) { List<Integer>[] g = new ArrayList[n]; Arrays.setAll(g, _ -> new ArrayList<>()); for (int[] e : edges) { int x = e[0]; int y = e[1]; g[x].add(y); g[y].add(x); } dfs(0, -1, g, values, k); return ans; } // 返回子树 x 的点权和 private long dfs(int x, int fa, List<Integer>[] g, int[] values, int k) { long sum = values[x]; for (int y : g[x]) { if (y != fa) { // 避免访问父节点 // 加上子树 y 的点权和，得到子树 x 的点权和 sum += dfs(y, x, g, values, k); } } ans += sum % k == 0 ? 1 : 0; return sum; } }

Java 版本用long累加点权和，防止n较大时权值求和溢出int范围，这是值得注意的工程细节（Rust 版同样使用i64，Go 版由于values与k均为int且竞赛环境按 32 位/64 位平台适配，保持int即可）。

C++

class Solution { public: int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) { vector<vector<int>> g(n); for (auto& e : edges) { int x = e[0], y = e[1]; g[x].push_back(y); g[y].push_back(x); } int ans = 0; // 返回子树 x 的点权和 auto dfs = & -> long long { long long sum = values[x]; for (int y : g[x]) { if (y != fa) { // 避免访问父节点 // 加上子树 y 的点权和，得到子树 x 的点权和 sum += dfs(y, x); } } ans += sum % k == 0; return sum; }; dfs(0, -1); return ans; } };

C++ 使用 C++23 的this auto&& dfs递归 lambda 自引用技巧，以long long做累加，同样规避溢出。

Go（与仓库实现完全一致）

func maxKDivisibleComponents(n int, edges [][]int, values []int, k int) (ans int) { g := make([][]int, n) for _, e := range edges { x, y := e[0], e[1] g[x] = append(g[x], y) g[y] = append(g[y], x) } // 返回子树 x 的点权和 var dfs func(int, int) int dfs = func(x, fa int) int { s := values[x] for _, y := range g[x] { if y != fa { // 避免访问父节点 // 加上子树 y 的点权和，得到子树 x 的点权和 s += dfs(y, x) } } if s%k == 0 { ans++ } return s } dfs(0, -1) return }

Go 版本利用命名返回值(ans int)：dfs闭包直接对ans计数，s%k == 0为真时ans++，函数结束时直接return返回命名结果。这段代码与仓库 leetcode/biweekly/114/d/d.go 中的实现逐行一致。

JavaScript

var maxKDivisibleComponents = function(n, edges, values, k) { const g = Array.from({ length: n }, () => []); for (const [x, y] of edges) { g[x].push(y); g[y].push(x); } let ans = 0; // 返回子树 x 的点权和 function dfs(x, fa) { let sum = values[x]; for (const y of g[x]) { if (y !== fa) { // 避免访问父节点 // 加上子树 y 的点权和，得到子树 x 的点权和 sum += dfs(y, x); } } ans += sum % k === 0 ? 1 : 0; return sum; } dfs(0, -1); return ans; };

Rust

impl Solution { pub fn max_k_divisible_components(n: i32, edges: Vec<Vec<i32>>, values: Vec<i32>, k: i32) -> i32 { let n = n as usize; let mut g = vec![vec![]; n]; for e in edges { let x = e[0] as usize; let y = e[1] as usize; g[x].push(y); g[y].push(x); } // 返回子树 x 的点权和 fn dfs(x: usize, fa: usize, g: &[Vec<usize>], values: &[i32], k: i64, ans: &mut i32) -> i64 { let mut sum = values[x] as i64; for &y in &g[x] { if y != fa { // 避免访问父节点 // 加上子树 y 的点权和，得到子树 x 的点权和 sum += dfs(y, x, g, values, k, ans); } } if sum % k == 0 { *ans += 1; } sum } let mut ans = 0; dfs(0, 0, &g, &values, k as i64, &mut ans); ans } }

Rust 版本将k转为i64、sum也用i64，通过&mut ans在递归中累计计数；根节点传入fa = 0（自环不会真正发生访问，因为0号节点不会是自己的邻居），同样达到"根不计数父边"的效果。

各版本差异小结

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。每个节点恰好进入一次 DFS，边各遍历一次，总操作量与n成正比。
• 空间复杂度：$\mathcal{O}(n)$。主要消耗在邻接表g（存储2(n−1)条有向边记录）以及递归调用栈的深度（最坏为链状树的深度n）。

对于n ≤ 10^5量级的数据，线性复杂度可以轻松通过。

仓库实战：Go 实现、测试驱动与用例数据

本仓库将上述题解沉淀为标准目录结构：每个题目目录包含题解文档 / 源码 / 测试 / 数据四个文件。

1. 源码实现 d.go

仓库中的实现与上文 Go 版本完全一致，采用package main顶层声明函数，方便直接编译运行与测试框架调用：

• 第 4–10 行：由edges构建无向邻接表g，每条边在两端各记录一次；
• 第 11–23 行：定义递归闭包dfs，跳过父节点fa，后序累加子树点权和并计数；
• 第 24 行：从根节点0出发，父节点传入-1（哨兵值，保证不会访问到不存在的节点）。

2. 自动化测试 d_test.go

测试文件由本仓库模板生成（文件头注明Code generated by copypasta/template/leetcode/generator_test.go），核心只有一行：

if err := testutil.RunLeetCodeFuncWithFile(t, maxKDivisibleComponents, "d.txt", targetCaseNum); err != nil { t.Fatal(err) }

它调用测试基础设施 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile：该函数通过反射自动解析d.txt中每组测试输入，将字符串按类型转换为函数实参并调用被测函数，再与期望输出比对。这意味着新增题目只需准备数据文件，无需手写断言，这也是本仓库能高效维护上千道题解的关键工程设计。测试文件末尾还保留了两条题源 URL 注释，方便回溯出处。

3. 测试用例数据 d.txt

数据文件采用"输入 + 期望输出"交替的格式，共 2 组用例：

5 [[0,2],[1,2],[1,3],[2,4]] [1,8,1,4,4] 6 2 7 [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] [3,0,6,1,5,2,1] 3 3

• 用例一：n = 5，树边[[0,2],[1,2],[1,3],[2,4]]，权值[1,8,1,4,4]，k = 6，答案为2。验证思路：以 2 为根，子树 2 的点权和为1+8+1+4+4=18，是 6 的倍数但根不可删父边；子树 3 和为 4（不可整除），子树 4 和为 4（不可整除），子树 0 和为 1（不可整除），子树 1 的和为8+1+4=13（不可整除）——实际上可切出的是以 2 为根的整块（总和 18 是 6 的倍数），切 1 次得 2 块，符合答案。
• 用例二：n = 7，k = 3，答案为3。整棵权值和为3+0+6+1+5+2+1=18是 3 的倍数，DFS 可统计出 3 个"子树和能被 3 整除"的子树，对应删除 2 条边后得到 3 个连通块。

运行go test于 leetcode/biweekly/114/d 目录即可复现这两组验证。

相似题目与延伸思考

题解末尾推荐的相似题目为LeetCode 2440「创建价值相同的连通块」（create-components-with-same-value）。两题同属"树 + 连通块点权和约束"家族：

• 本题约束是"每个连通块点权和为k的倍数"，答案直接由 DFS 计数得到；
• 2440 的约束是"每个连通块点权和相同"，通常需要先枚举目标值（总和的因子），再做同样的 DFS 切分判定。

两者共享同一套"子树和 + 可切分判定"的后序遍历框架，区别仅在约束条件与是否需要对目标值进行枚举。吃透本文的证明链（封闭性 → 充要条件 → 可删就删），再遇到同族题目时只需替换判定谓词即可。

总结

本文从一道周赛压轴题（Biweekly Contest 114 D 题）出发，完整走通了四条主线：

1. 问题转化：最大化连通块数 ⟺ 最大化删边数 + 1；
2. 数学引理：k的倍数对加法封闭，其逆否命题保证了"不可整除块永远存在瑕疵"，从而推出删边充要条件——两切块点权和均被k整除；
3. 算法实现：一次自底向上 DFS 计算子树点权和，s % k == 0即对应一个可删除的边/一个最终连通块，答案直接累加，无需额外 +1；
4. 工程落地：六种语言的同构实现 + 本仓库 Go 源码、反射驱动测试与样例数据的完整闭环，复杂度均为 $\mathcal{O}(n)$ 时间、$\mathcal{O}(n)$ 空间。

这道题是"树形结构 + 数论性质 + 贪心"三要素组合的经典范例，其证明方式（从数论封闭性推出树上的剪枝合法性）值得在后续树形 DFS 题目中反复迁移。

• 科学计算