科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-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为根的子树点权和初始化s values[x]包含节点自身的权值遍历x的所有邻居y跳过y fa避免走回父节点形成环递归累加s dfs(y, x)得到子树点权和判断s % k 0成立则ans返回s给父层使用。由于是后序自底向上累加每个节点恰好被访问一次总复杂度为线性。六种语言实现题解为同一算法提供了六种主流语言的实现下面逐一完整给出。它们逻辑完全一致仅语法不同Python3class 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 ansPython 版本利用nonlocal ans在嵌套函数中直接修改外层计数ans s % k 0将布尔值隐式转为 0/1 累加代码极简。Javaclass Solution { private int ans; public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) { ListInteger[] 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, ListInteger[] 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 版同样使用i64Go 版由于values与k均为int且竞赛环境按 32 位/64 位平台适配保持int即可。Cclass Solution { public: int maxKDivisibleComponents(int n, vectorvectorint edges, vectorint values, int k) { vectorvectorint 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 使用 C23 的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 中的实现逐行一致。JavaScriptvar 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; };Rustimpl Solution { pub fn max_k_divisible_components(n: i32, edges: VecVeci32, values: Veci32, 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: [Vecusize], 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号节点不会是自己的邻居同样达到根不计数父边的效果。各版本差异小结语言邻接表构建子树和类型计数方式Python3列表推导式intnonlocal ans 布尔累加JavaArrays.setAll ArrayListlong成员变量 ansCvectorvector long longlambda 捕获 ansGomake([][]int)int命名返回值闭包内 ansJavaScriptArray.fromnumber闭包内 ans 布尔Rustvec![vec![]; n]i64mut ans 指针累加复杂度分析时间复杂度$\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 的点权和为1814418是 6 的倍数但根不可删父边子树 3 和为 4不可整除子树 4 和为 4不可整除子树 0 和为 1不可整除子树 1 的和为81413不可整除——实际上可切出的是以 2 为根的整块总和 18 是 6 的倍数切 1 次得 2 块符合答案。用例二n 7k 3答案为3。整棵权值和为306152118是 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数学引理k的倍数对加法封闭其逆否命题保证了不可整除块永远存在瑕疵从而推出删边充要条件——两切块点权和均被k整除算法实现一次自底向上 DFS 计算子树点权和s % k 0即对应一个可删除的边/一个最终连通块答案直接累加无需额外 1工程落地六种语言的同构实现 本仓库 Go 源码、反射驱动测试与样例数据的完整闭环复杂度均为 $\mathcal{O}(n)$ 时间、$\mathcal{O}(n)$ 空间。这道题是树形结构 数论性质 贪心三要素组合的经典范例其证明方式从数论封闭性推出树上的剪枝合法性值得在后续树形 DFS 题目中反复迁移。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode 2658「网格中的最大鱼数」DFS 连通块求和全解基于 codeforces-go 仓库的 Python/Java/C/Go 四语言实现与测试验证LeetCode 2658「网格中的最大鱼数」DFS 连通块求和全解基于 codeforces go 仓库的 Python/Java/C/Go 四语言实现科学计算LeetCode-Go 题解1005. Maximize Sum Of Array After K NegationsK 次取反后最大化数组和LeetCode Go 题解1005. Maximize Sum Of Array After K NegationsK 次取反后最大化数组和 导读 本文示例工程Blender 插件指南16 个工具搭好 3D 建模全流程Blender 插件指南16 个工具搭好 3D 建模全流程 还在为繁琐的 3D 设计流程发愁吗开源项目 awesome blender 把数百个经过筛选的插文档教程上一篇Godot PCK解包工具轻松提取游戏资源的智能解决方案下一篇Godot PCK解包工具专业高效的Godot游戏资源提取方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考