LCC/Moose '18 Contest 3 S4 - Christmas Tree

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem types

The Mackenzie programming club has decided to celebrate the holidays by decorating a tree. Being the programming club, their tree is of course a tree rooted at R with N vertices numbered from 1 to N. They would like to light up their tree by placing a colourful LED on each vertex of the tree.

The subtree rooted at a vertex is called colourful if every descendant of the vertex (including the vertex itself) has a different colour. The club would like at least M colourful subtrees in their tree. Since buying LEDs of different colours is expensive, the club would like to use as few colours as possible to achieve their goal. Could you help them out?

Input Specification

The first line of input contains a three integers N, R, M (1 \le N \le 2 \times 10^5, 1 \le R, M \le N), the number of vertices in the tree, the root vertex of the tree, and the number of colourful subtrees desired, respectively. The next N-1 lines each contain two integers A, B (1 \le A, B \le N) representing an edge in the tree.

For 30\% of the points, 1 \le N \le 5 000.

Output Specification

The minimum number of different colours required in order to create a tree with at least M colourful subtrees.

Sample Input 1

3 1 2
1 2
1 3

Sample Output 1

1

Sample Input 2

5 1 3
1 2
2 3
3 4
4 5

Sample Output 2

3

Comments

There are no comments at the moment.