BalancingTrees
2018 TCO Semi 2 · 2018-11-14 · by lg5293
Problem Statement
Consider a rooted tree with weighted nodes. A node in this tree is called weight-balanced if all of its child subtrees have the same total weight. (In particular, a leaf node is always weight-balanced.) A tree is called weight-balanced if every node is weight-balanced.
You are given one particular rooted tree with node weights. The tree has N nodes, numbered from 0 to N-1 in such a way that the parent always has a smaller number than the child. For each i between 0 and N-2, inclusive, the parent of vertex i+1 is vertex p[i]. The weight of node i is w[i].
You would like to make the tree weight-balanced by modifying the weights of its vertices. The cost of modifying a node is equal to the absolute value of the difference between its old and new value. Note that the new weights can be any real numbers.
Return the minimum total cost needed to make the tree weight-balanced.
Notes
- Your answer will be accepted if it has absolute or relative error at most 1e-9.
Constraints
- N will be between 1 and 251, inclusive.
- p will have exactly N-1 elements.
- The i-th element of p[i] will be between 0 and i, inclusive.
- w will have exactly N elements.
- Each element of w will be between -10^9 and 10^9, inclusive.
{0,0,0}
{3,1,2,1}
Returns: 1.0
In this case, we can decrease the weight of node 2 from 2 to 1 so that all children of node 0 have weight 1.
{0,0,1,1}
{0,4,7,1,2}
Returns: 1.0
In this case, it is optimal to change nodes 4 and 5 to cost 1.5 each. After the change all nodes will be weight-balanced: each child subtree of node 0 will have total weight 7 and each child subtree of node 1 will have total weight 1.5.
{0,0,0,1,1,1,2,2,2,3,3,3}
{0,-1,2,-3,9,-8,7,-6,5,-4,3,-2,1}
Returns: 43.0
Don't forget that some weights can be negative.
{0,1,0}
{0,1000000000,1000000000,1000000000}
Returns: 1.0E9
One optimal solution is to change the value of node 3 to 2000000000.
{}
{-1000000000}
Returns: 0.0
Submissions are judged against all 357 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BalancingTrees with a public method double minCost(vector<int> p, vector<int> w) · 357 test cases · 2 s / 256 MB per case