TREEBAL - Editorial

PROBLEM LINKS

Practice
Contest

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.