DeepSeek LeetCode 2872. 可以被 K 整除连通块的最大数目 Java实现

javaimport java.util.ArrayList;import java.util.List;class Solution {private ListInteger[] graph;private int[] values;private int k;private int cuts; // 切掉的边数也是得到的所有有效子树块数不包括根部分public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {this.values values;this.k k;this.cuts 0;// 构建邻接表graph new ArrayList[n];for (int i 0; i n; i) {graph[i] new ArrayList();}for (int[] e : edges) {graph[e[0]].add(e[1]);graph[e[1]].add(e[0]);}// 后序遍历得到整棵树的和模 klong rootMod dfs(0, -1);// 总有效块数 切出的子树块数 (根部分是否有效)return cuts (rootMod 0 ? 1 : 0);}private long dfs(int node, int parent) {long sum values[node] % k; // 当前节点值模 kfor (int nei : graph[node]) {if (nei parent) continue;sum dfs(nei, node);}sum % k;// 如果当前子树和能被 k 整除且不是根节点则切掉与父节点的边if (sum 0 node ! 0) {cuts; // 切出一个有效连通块return 0; // 该子树对父节点不再有贡献}return sum;}}