PROBLEM LINKS
DIFFICULTY
hard
PREREQUISITES
dp, binary search tree, maintaining lower convex hull of line, small to large trick
PROBLEM
You are given a tree with weighted edges. For each edge, you are given initial value c_i,
and a parameter d_i. You can change it to x by paying a cost equal to |d_i * (x - c_i)|.
You want that weight of edges of each path from root to any leaf should have equal value.
Find out minimum cost that you require to achieve this. Also, find out the updated weights of each edge.
QUICK EXPLANATION
The function |d_i * (x - c_i)| can be thought as of two line segments d_i * (x - c_i) for x \geq c_i and |d_i * (c_i - x)| for x \leq c_i.
At each node, we maintain a lower convex hull of the line segments. For a node, we can merge the lower convex hull of children nodes to find the lower convex hull of the node. This merging should be done by a trick sometimes stated as small to large trick. We merge the light children into the heaviest child.
Overall we get \mathcal{O}(n \, {(log n)}^2) time complexity.
EXPLANATION
A detailed explanation about this will be posted very soon.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
EDITORIALIST’S SOLUTION
Can be found here.