⚡Flashcard Drill➔
NeetCode #618LC-2872HardGraphs
← Back to All Problems

#618 · #2872 · Maximum Number of K-Divisible Components(可以被 K 整除连通块的最大数目)

📌 Problem Statement & Constraints

You are given a tree of n nodes, edges, values for each node, and an integer k. Remove some edges so that every resulting component has a sum divisible by k. Return the maximum number of components. Constraints: 1 <= n <= 3 * 10^4, 1 <= k <= 10^9, 1 <= values[i] <= 10^9; the total sum is divisible by k.

💡 Core Algorithmic Approaches

  1. A post-order DFS: for each node, compute the sum of its component (its value plus the un-cut children's sums).
  2. If that sum is divisible by k, cut the edge to the parent -- this component is complete, and the parent receives 0.
  3. Cutting greedily bottom-up is optimal: a subtree that can be cut should be cut as early as possible.
  4. The total sum being divisible by k guarantees the root's remainder is also divisible, so all components are valid.

💻 Benchmark Python3 Implementation

class Solution:
    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        from collections import defaultdict
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        self.count = 0

        def dfs(node: int, parent: int) -> int:
            total = values[node]
            for nxt in g[node]:
                if nxt == parent:
                    continue
                total += dfs(nxt, node)    # gather the un-cut children
            if total % k == 0:             # this component is complete
                self.count += 1
                return 0                   # the parent receives nothing
            return total                   # the remainder flows upward

        dfs(0, -1)
        return self.count

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one post-order traversal.
💾 Space Complexity
O(n) for the adjacency list and the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Counting only the root component: every cut creates a component, and the root's component is counted when its total is divisible.
  • Returning the total instead of 0 after a cut: the parent would double-count the cut-off sum.
  • Trying to enumerate all edge subsets: exponential.
  • Forgetting the parent guard: the DFS would loop on the undirected tree.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems