Split a Tree Into Equal Parts

Hard

You are given a tree of n nodes numbered 0 to n - 1. Node i has the weight weights[i], and links[j] = [a, b] is a link between nodes a and b. You may cut some of the links, and the tree falls apart into pieces. The weight of a piece is the sum of the weights of its nodes. Return the maximum number of links you can cut so that all resulting pieces have the same weight. If no split works, return 0.

Example 1

weights=[3, 1, 2, 3, 3], links=[[0, 1], [1, 2], [1, 3], [3, 4]] → 3

The total weight is 12. Cutting links [0, 1], [1, 3] and [3, 4] leaves the parts {0}, {1, 2}, {3}, {4}, each weighing 3. That is 3 cuts, and no more are possible.

Example 2

weights=[4, 2, 5], links=[[0, 1], [1, 2]] → 0

The total weight is 11, a prime, so the tree cannot be split into several equal parts.

Example 3

weights=[7], links=[] → 0

Constraints

1 ≤ n ≤ 2·10⁴, n = len(weights)
1 ≤ weights[i] ≤ 50
len(links) = n − 1, and the links form a tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Array Math Enumeration

Similar problems

Nearest Coprime Ancestor Hard Other Orders for the Same Search Tree Hard Where Moss Species Meet Hard Tree Path Without Twin Neighbours Hard Meeting Point on a Route Hard

Input

weights=[3, 1, 2, 3, 3], links=[[0, 1], [1, 2], [1, 3], [3, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 47 tests on the server, hidden ones included.