Областная олимпиада по информатике, 2018 год, 10-11 класс

(Опять деревья) Дается неориентированное дерево из $n$ вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более $k$ операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.

Формат входных данных:

В первой строке содержатся числа $n$ и $k$ ($0 \le k \le n - 1$) - количество вершин и максимальное количество вершин которое можно удалить.
В следующих $n-1$ строках следует описание графа.
В каждой строке содержатся числа $u$ и $v$ ($1 \le u, v \le n$) - означает что существует неориентированное ребро между вершиной $u$ и вершиной $v$.

Формат выходных данных:

Выведите ровно одно число - минимальный диаметр который можно получить удалив не более $k$ вершин.

Примеры:

1.Вход:

5 2
1 4
3 2
1 2
5 2

Ответ:

2

2.Вход:

14 5
13 2
10 4
6 12
8 11
11 13
5 14
10 3
11 5
12 1
9 7
11 10
10 9
6 10

Ответ:

3

Система оценки:

Задача содержит 100 тестов, каждая из которых весят 1 балл.
Ограничения которые присутствуют в тестах:

• 10 теста: $n \le 20$
  
• 10 тестов: $n \le 100$
  
• 5 тестов: $k = 0$
  
• 24 тестов: $n \le 2000$
  
• 51 тестов: $n \le 5000$
  

( Askhat Zhalgasov )