Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Process the tree from leaves inward. If a leaf-side component's sum is divisible by k, cutting it off adds a valid component without changing the remaining sum modulo k. Otherwise its sum must stay attached to the rest of the tree. Taking every available divisible cut maximizes the component count.

Approach

Build adjacency and remaining-degree counts, then queue all leaves. When removing a leaf, count its accumulated value as a component if divisible by k; otherwise pass that value to its remaining neighbor. Decrease the neighbor's degree and enqueue it when it becomes a leaf. The code updates values in place. The guaranteed divisible total ensures the final remainder also forms a valid component, including the single-node case.

class Solution:
    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        if n == 1:
            return 1

        adj = defaultdict(list)
        indegree = defaultdict(int)

        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
            indegree[a] += 1
            indegree[b] += 1

        q = deque(node for node in range(n) if indegree[node] == 1)
        res = 0

        while q:
            node = q.popleft()
            indegree[node] -= 1
            to_add = 0
            if values[node] % k == 0:
                res += 1
            else:
                to_add = values[node]
            for nei in adj[node]:
                if indegree[nei] == 0:
                    continue
                indegree[nei] -= 1
                values[nei] += to_add
                if indegree[nei] == 1:
                    q.append(nei)

        return res

Complexity analysis

Let n be the number of tree nodes. Time: O(n). Auxiliary space: O(n) for adjacency, degrees, and the leaf queue.