Editorial for BSSPC '21 J6 - Lakshy and Orz Trees


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: sushi

The problem is essentially asking for each node in the tree to have at most 2 subtrees, with the exception of the root having 3.

We can approach this problem greedily. The optimal solution is for every node u (other than the root), to keep the 2 most expensive subtrees (or the 3 most expensive, for the root) and remove the rest. We define the cost of a subtree to be the cost of that subtree to become an Orz Tree. The cost is equivalent to the total weight of the subtree (not including the root of the subtree) and minus the sum of the most expensive subtrees. For leaves, their cost is simply their weight. This is akin to bottom-up tree dp.

Time Complexity: \mathcal O(N)


Comments

There are no comments at the moment.