n nodes numbered 0 to n - 1; its edges are listed in edges, where edges[i] = [a, b]. Each node has a weight values[i], and you are also given a number k. The sum of all weights is a multiple of k.
You may delete any set of edges, possibly none. The tree falls apart into pieces, and the weight of a piece is the sum of its node weights. A cut is good if every piece weighs a multiple of k.
Return the largest number of pieces over all good cuts.n=4, edges=[[0, 1], [1, 2], [1, 3]], values=[2, 4, 3, 5], k=7 → 1
The total weight is 14. Cutting 1–3 leaves parts of weight 5 and 9, cutting 1–2 leaves 3 and 11, cutting 0–1 leaves 2 and 12; none is a multiple of 7. So the tree stays whole: one part.
n=5, edges=[[0, 1], [0, 2], [2, 3], [2, 4]], values=[1, 2, 3, 4, 2], k=3 → 2
Cutting off node 3 or node 4 fails, since 4 and 2 are not multiples of 3. Deleting edge 0–2 gives {2, 3, 4} with weight 9 and {0, 1} with weight 3. No third piece is possible, so the answer is 2.
n=1, edges=[], values=[0], k=4 → 1
values is a multiple of kn=4, edges=[[0, 1], [1, 2], [1, 3]], values=[2, 4, 3, 5], k=7
1
Run checks the first 3 tests in your browser. Submit checks all 70 tests on the server, hidden ones included.