#2872

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximum Number of K-Divisible Components

Determine the maximum number of connected components in a tree where each component sum is divisible by k using DFS.

Problem Statement

You are given a tree with n nodes labeled from 0 to n - 1 and an array edges where edges[i] = [ai, bi] represents an undirected edge connecting nodes ai and bi. Each node has an associated value provided in an array values. Additionally, you are given an integer k. Your task is to split the tree by removing edges so that the sum of node values in each resulting component is divisible by k.

Return the maximum number of connected components obtainable under these rules. The sum of all node values is guaranteed to be divisible by k. Splitting should consider valid subtree sums from any rooted node, and the tree can be rooted arbitrarily for traversal purposes.

Examples

Example 1

Input: n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6

Output: 2

We remove the edge connecting node 1 with 2. The resulting split is valid because:

The value of the component containing nodes 1 and 3 is values[1] + values[3] = 12.
The value of the component containing nodes 0, 2, and 4 is values[0] + values[2] + values[4] = 6. It can be shown that no other valid split has more than 2 connected components.

Example 2

Input: 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

Output: 3

We remove the edge connecting node 0 with 2, and the edge connecting node 0 with 1. The resulting split is valid because:

The value of the component containing node 0 is values[0] = 3.
The value of the component containing nodes 2, 5, and 6 is values[2] + values[5] + values[6] = 9.
The value of the component containing nodes 1, 3, and 4 is values[1] + values[3] + values[4] = 6. It can be shown that no other valid split has more than 3 connected components.

Constraints

1 <= n <= 3 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
values.length == n
0 <= values[i] <= 109
1 <= k <= 109
Sum of values is divisible by k.
The input is generated such that edges represents a valid tree.

Solution Approach

Root the Tree and Initialize DFS

Choose node 0 as the root to facilitate a depth-first search. Initialize a DFS function that will traverse the tree, passing parent information to avoid revisiting nodes. Each DFS call should return the sum of the subtree rooted at the current node modulo k.

Aggregate Subtree Sums and Count Components

During DFS, compute the sum of each child subtree including the current node. If a child's subtree sum modulo k is 0, it forms a valid component and can be detached, incrementing the component count. Continue propagating sums upward to correctly detect k-divisible components across the tree.

Return Maximum Components

After DFS traversal completes, the total number of detached valid subtrees plus one for the remaining tree gives the maximum number of k-divisible components. This ensures all splits are counted without double-counting nodes or missing valid component formations.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The DFS visits each node once and processes each edge once, resulting in O(n) time complexity. Storing tree adjacency and tracking DFS recursion uses O(n) space, including the recursion stack.

What Interviewers Usually Probe

Check whether the sum of values in subtrees is divisible by k after each DFS call.
Consider edge removal only when a subtree sum modulo k equals zero to maximize component count.
Be mindful of tree rooting and parent-child relationships to avoid revisiting nodes.

Common Pitfalls or Variants

Common pitfalls

Failing to propagate the correct modulo k sum from child to parent, causing undercounting components.
Counting a subtree as a component before verifying its sum modulo k equals zero.
Ignoring the necessity of rooting the tree to track parent-child relationships correctly during DFS.

Follow-up variants

Modify the problem to find the maximum number of components divisible by a variable k for multiple queries.
Allow negative node values and adjust DFS aggregation to handle negative modulo correctly.
Compute minimum number of edges to remove instead of maximum components, which changes DFS decision logic.

FAQ

What is the main pattern used in Maximum Number of K-Divisible Components?

The problem uses binary-tree traversal and state tracking, specifically depth-first search to accumulate subtree sums and detect k-divisible components.

How do I handle the modulo k calculation in the DFS?

At each node, return the sum of its value plus child subtree sums modulo k. If a child sum modulo k is zero, it counts as a valid component.

Can the tree be rooted at any node?

Yes, but rooting at node 0 simplifies DFS implementation and ensures consistent parent-child tracking for aggregation.

What if no edge removal yields k-divisible components?

In that case, the entire tree counts as a single component, since the sum of all nodes is guaranteed divisible by k.

What is the time complexity for this problem?

Using DFS, the time complexity is O(n) since each node and edge is processed exactly once, making it efficient for large trees.

terminal

Solution

Solution 1: DFS

We note that the problem guarantees the sum of all node values in the entire tree is divisible by $k$. Therefore, if we remove a subtree whose sum of elements is divisible by $k$, the sum of node values in each of the remaining connected components must also be divisible by $k$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

Continue Practicing

#2867 count valid paths in a tree #2920 maximum points after collecting coins from all nodes #2925 maximum score after applying operations on a tree