Maximum Number of K-Divisible Components

An undirected tree has n nodes labeled 0 through n - 1. The array edges gives its connections, and values[i] is the nonnegative value at node i.

You may remove any number of edges, including none. The remaining connected components form a valid split when the sum of the node values in every component is divisible by k.

Return the largest number of components in a valid split. The sum of all node values is guaranteed to be divisible by k. A component with sum zero is also divisible by k.

Diagram nodes show node index:value.

Example 1:

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

Output: 3

Explanation: Remove edges [1,2] and [2,3]. The components are {0,1}, {2}, and {3}, with sums 6, 3, and 3. All are divisible by 3. Nodes 0 and 1 cannot form valid separate components, so the maximum is 3.

Example 2:

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

Output: 3

Explanation: Remove both edges. The three single-node components have sums 0, 5, and 5, all divisible by 5. Zero is divisible by every positive k, so all 3 nodes can be separate components.

Example 3:

Input: n = 3
edges = [[0,1],[1,2]]
values = [1,1,1]
k = 3

Output: 1

Explanation: The whole tree has sum 3. Any removed edge leaves a component with sum 1 or 2, which is not divisible by 3. Keep both edges to obtain the only valid split, with 1 component.

Constraints:

• 1 <= n <= 30000
• edges.length == n - 1
• Each edge contains two distinct integer labels between 0 and n - 1.
• The edges form a connected, undirected tree.
• values.length == n
• 0 <= values[i] <= 1000000000
• 1 <= k <= 1000000000
• The sum of values is divisible by k.

Topics

Tree Depth-First Search

Company Tags

Please upgrade to NeetCode Pro to view company tags.