Processing math: 100%

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


(Опять деревья) Дается неориентированное дерево из n вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более k операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
Формат входных данных:
В первой строке содержатся числа n и k (0kn1) - количество вершин и максимальное количество вершин которое можно удалить.
В следующих n1 строках следует описание графа.
В каждой строке содержатся числа u и v (1u,vn) - означает что существует неориентированное ребро между вершиной 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 )
посмотреть в олимпиаде

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