You are given a rooted tree with n nodes labeled 1..n (root is node 1). Each node i initially contains stones[i] stones.
Define the subtree sum of a node as the total number of stones in that node’s subtree (including itself).
A node is considered balanced if all of its children’s subtree sums are equal. (Leaves are automatically balanced.)
You are allowed to perform the following operation any number of times:
-
Choose any node and
add 1 stone
to it.
Task: Return the minimum number of stones you must add so that every node in the tree is balanced.
-
n
— number of nodes
-
edges
—
n-1
undirected edges describing the tree
-
stones[1..n]
— initial stone counts (non-negative integers)
Output
-
An integer: the minimum total number of added stones.
Constraints (typical)
-
1 ≤ n ≤ 2e5
-
0 ≤ stones[i] ≤ 1e9
(You should aim for an O(n) or O(n log n) solution.)