Editorial for BSSPC '21 J6 - Lakshy and Orz Trees
Submitting an official solution before solving the problem yourself is a bannable offence.
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)~