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.