# Maximum Number of K-Divisible Components
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-k-divisible-components)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-k-divisible-components
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree
---
## Problem
There is an undirected tree with `n` nodes labeled from `0` to `n - 1`. You are given the integer `n` and a 2D integer array `edges` of length `n - 1`, where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

You are also given a **0-indexed** integer array `values` of length `n`, where `values[i]` is the **value** associated with the `ith` node, and an integer `k`.

A **valid split** of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by `k`, where the **value of a connected component** is the sum of the values of its nodes.

Return _the **maximum number of components** in any valid split_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-number-of-k-divisible-components/image0.jpg) 

**Input:** n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
**Output:** 2
**Explanation:** 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:**

![](https://assets.glich.co/dsa/maximum-number-of-k-divisible-components/image1.jpg) 

**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
**Explanation:** 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.

# Approaches
## Brute Force by Trying All Edge Cuts
This approach exhaustively checks every possible way to split the tree by considering all subsets of edges to remove. For each of the `2^(n-1)` possible ways to cut edges, it verifies if the resulting components form a valid split. A split is valid if the sum of values in every component is divisible by `k`. The algorithm keeps track of the maximum number of components across all valid splits.
**Time:** O(2^N * N). There are `2^(n-1)` subsets of edges. For each subset, building the graph and finding components takes O(N + E') where E' is the number of edges, which is at most N-1. So, it's O(N) for each check. The total time is O(2^(n-1) * N). · **Space:** O(N) for storing the adjacency list, visited array, and queue for BFS for each of the `2^(n-1)` configurations.
**Pros:** It is a direct implementation of the problem statement and is guaranteed to be correct.; It is conceptually simple to understand.
**Cons:** The time complexity is exponential, `O(2^N * N)`, which is extremely slow and only feasible for very small `N`.; It is highly impractical for the given constraints of the problem (`n` up to 30,000).
### Explanation
The brute-force method systematically explores the entire solution space. Since the tree has `n-1` edges, and each edge can either be kept or removed, there are `2^(n-1)` possible resulting graphs (forests).

We can use an integer `i` from `0` to `2^(n-1) - 1` as a bitmask to represent which edges are removed. For each mask `i`, we build the corresponding graph. Then, we traverse this graph to identify its connected components. For each component, we sum up the values of its nodes. If all these sums are divisible by `k`, we have found a valid split. We then compare the number of components in this split with the maximum number found so far and update it if necessary.

This process is repeated for all `2^(n-1)` possibilities to guarantee finding the maximum number of components.

```java
import java.util.*;

class Solution {
    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        if (n == 1) {
            return values[0] % k == 0 ? 1 : 0;
        }
        int maxComponents = 0;
        int numEdges = n - 1;

        for (int i = 0; i < (1 << numEdges); i++) {
            List<List<Integer>> adj = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                adj.add(new ArrayList<>());
            }

            // Build adjacency list based on which edges are kept
            for (int j = 0; j < numEdges; j++) {
                if ((i & (1 << j)) == 0) { // Keep the edge if the bit is 0
                    int u = edges[j][0];
                    int v = edges[j][1];
                    adj.get(u).add(v);
                    adj.get(v).add(u);
                }
            }

            // Find components and check validity
            boolean[] visited = new boolean[n];
            int currentComponents = 0;
            boolean isSplitValid = true;

            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    currentComponents++;
                    long componentSum = 0;
                    Queue<Integer> q = new LinkedList<>();
                    q.add(j);
                    visited[j] = true;

                    while (!q.isEmpty()) {
                        int u = q.poll();
                        componentSum += values[u];
                        for (int v : adj.get(u)) {
                            if (!visited[v]) {
                                visited[v] = true;
                                q.add(v);
                            }
                        }
                    }

                    if (componentSum % k != 0) {
                        isSplitValid = false;
                        break;
                    }
                }
            }

            if (isSplitValid) {
                maxComponents = Math.max(maxComponents, currentComponents);
            }
        }
        // Since total sum is divisible by k, the whole tree is a valid component.
        // So maxComponents will be at least 1.
        return maxComponents;
    }
}
```
### Algorithm
- Iterate through every possible subset of the `n-1` edges. There are `2^(n-1)` such subsets.
- Each subset represents a way to partition the tree. A bitmask from `0` to `2^(n-1) - 1` can represent these subsets, where the `i`-th bit being set means the `i`-th edge is removed.
- For each partition:
  - Construct the graph formed by the edges that were not removed.
  - Find all connected components in this graph using a traversal algorithm like BFS or DFS.
  - For each component, calculate the sum of the `values` of its nodes.
  - Check if all component sums are divisible by `k`.
  - If the split is valid, update the maximum number of components found so far.
- Return the maximum number of components found across all valid splits.

## Greedy Post-order Traversal (DFS)
A highly efficient approach using a single Depth-First Search (DFS) traversal. The core idea is to perform a post-order traversal, calculating the sum of values for each subtree. Whenever a subtree's sum is found to be divisible by `k`, we can greedily 'cut' this subtree from its parent to form a valid component. This greedy choice is optimal because it maximizes the number of components without preventing other potential cuts elsewhere in the tree. The problem guarantees that the total sum is divisible by `k`, ensuring that the remaining part of the tree also forms valid components.
**Time:** O(N). Building the adjacency list takes O(N) time as there are `n-1` edges. The DFS traversal visits each node and edge exactly once, which also takes O(N). · **Space:** O(N) for the adjacency list and the recursion stack. In the worst-case scenario of a skewed tree (like a path), the recursion depth can be O(N).
**Pros:** Extremely efficient, with a linear time complexity of O(N).; The implementation is concise and uses a standard DFS pattern.; It is guaranteed to find the optimal solution.
**Cons:** The greedy logic might not be immediately intuitive. Its correctness depends on the problem's property that the total sum of all node values is divisible by `k`.
### Explanation
This optimal solution leverages a post-order traversal (a form of DFS) to make greedy decisions. We can think of the process as starting from the leaves and moving up towards the root.

For any node `u`, we first recursively calculate the sums of the components rooted at its children. For each child `v`, the recursive call `dfs(v, u)` will return the sum of the values in the component containing `v` and its descendants (after any possible cuts within that subtree).

If the returned sum from a child `v`'s component is divisible by `k`, we have an opportunity. We can cut the edge `(u, v)`, creating a valid component from `v`'s subtree. This is always the best move to maximize components. We increment our component count and treat this child's contribution to `u`'s sum as zero.

If the sum is not divisible by `k`, we cannot cut the edge, so we must merge `v`'s component into `u`'s by adding its sum to `u`'s running total.

This logic can be implemented cleanly in a recursive DFS function that returns the sum of the current component to its parent. If a subtree's sum is divisible by `k`, we increment a counter and return 0, effectively signaling a cut. Otherwise, we return the actual sum.

```java
import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private int[] values;
    private int k;
    private int components;

    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            this.adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        this.values = values;
        this.k = k;
        this.components = 0;

        dfs(0, -1);

        return this.components;
    }

    private long dfs(int u, int parent) {
        // Use long to prevent overflow as sum of values can be large.
        long currentSum = values[u];

        for (int v : adj.get(u)) {
            if (v == parent) {
                continue;
            }
            currentSum += dfs(v, u);
        }

        if (currentSum % k == 0) {
            // This subtree can form a valid component.
            // We 'cut' it by not propagating its sum to the parent.
            components++;
            return 0;
        }

        // This subtree cannot form a component on its own yet.
        // Propagate its sum to the parent.
        return currentSum;
    }
}
```
### Algorithm
- First, represent the tree using an adjacency list.
- Initialize a global counter for components to zero.
- Perform a post-order traversal (DFS) on the tree, starting from an arbitrary root (e.g., node 0).
- Define a recursive helper function `dfs(node, parent)` that returns the sum of values in the subtree rooted at `node`.
- In `dfs(node, parent)`:
  - Initialize `currentSum` with `values[node]`.
  - Recursively call `dfs` for all children of `node` and add their returned sums to `currentSum`.
  - After processing all children, check if `currentSum` is divisible by `k`.
  - If `currentSum % k == 0`, it means the subtree rooted at `node` can form a valid component. We increment the global component counter and return `0` to the parent. Returning `0` effectively 'cuts' the subtree from its parent, as its sum is not passed up.
  - If `currentSum` is not divisible by `k`, we cannot cut the edge to the parent. We return `currentSum` to be merged with the parent's component sum.
- After the initial `dfs(0, -1)` call completes, the global counter will hold the maximum number of k-divisible components.

# Solutions
### Java

```java
class Solution {
private
  int ans;
private
  List<Integer>[] g;
private
  int[] values;
private
  int k;
public
  int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
    g = new List[n];
    Arrays.setAll(g, i->new ArrayList<>());
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    this.values = values;
    this.k = k;
    dfs(0, -1);
    return ans;
  }
private
  long dfs(int i, int fa) {
    long s = values[i];
    for (int j : g[i]) {
      if (j != fa) {
        s += dfs(j, i);
      }
    }
    ans += s % k == 0 ? 1 : 0;
    return s;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxKDivisibleComponents(int n, vector<vector<int>> &edges,
                              vector<int> &values, int k) {
    int ans = 0;
    vector<int> g[n];
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    function<long long(int, int)> dfs = [&](int i, int fa) {
      long long s = values[i];
      for (int j : g[i]) {
        if (j != fa) {
          s += dfs(j, i);
        }
      }
      ans += s % k == 0;
      return s;
    };
    dfs(0, -1);
    return ans;
  }
};

```

### Python

```python
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

```