Editorial for LCC/Moose '18 Contest 3 S4 - Christmas Tree


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: Ninjaclasher

We want M colourful subtrees in the tree, and that the colours in each of the subtrees is distinct. Thus, we can greedily choose the smallest M subtrees to make colourful. We can show this works because if we choose any subtree that is larger than the M^{th} smallest subtree, we need more colours, which is counter-intuitive.

The algorithm goes like this: Do a depth-first search (DFS) starting from the root R, each time inserting into an array the size of its subtree (the number of vertices in its children and itself). Then we can sort the array, and the answer is the M^{th} element in the array (1 indexed).

Time Complexity: \mathcal{O}(N)

Note: Some programmers who do contests on Codeforces may see that this problem is very similar to this problem. In fact, the algorithm is exactly the same. This problem was actually inspired by the Codeforces problem.


Comments

There are no comments at the moment.