#2440

Create Components With Same Value

candidate master · 1340 · lc hard +32 · verified · 53.3% accepted · 439 likes · top 44%

Description

An undirected tree has n nodes (labeled 0 to n - 1) with integer values given by nums. Partition its nodes into the maximum number of components such that every component's node values sum to the same value.

Return the maximum number of components achievable, or -1 if it is impossible.

Example 1:

Input: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]]

Output: 2

Explanation: The above figure shows how we can delete the edges [0,1] and [3,4]. The created components are nodes [0], [1,2,3] and [4]. The sum of the values in each component equals 6. It can be proven that no better deletion exists, so the answer is 2.

Example 2:

Input: nums = [2], edges = []

Output: 0

Explanation: There are no edges to be deleted.

Code

1

2

3

class Solution:
    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:

class Solution:
    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int: