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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
The problem is essentially asking for each node in the tree to have at most subtrees, with the exception of the root having
.
We can approach this problem greedily. The optimal solution is for every node (other than the root), to keep the
most expensive subtrees (or the
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:
Comments