Областная олимпиада по информатике, 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 балл.
Ограничения которые присутствуют в тестах:
( Askhat Zhalgasov )
посмотреть в олимпиаде

Комментарий/решение: