Областная олимпиада по информатике, 2018 год, 10-11 класс
(Опять деревья) Дается неориентированное дерево из n вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более k операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
В следующих n−1 строках следует описание графа.
В каждой строке содержатся числа u и v (1≤u,v≤n) - означает что существует неориентированное ребро между вершиной u и вершиной v.
Ограничения которые присутствуют в тестах:
посмотреть в олимпиаде
В данной задаче вам нужно минимизировать диаметр дерева применив не более k операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
Формат входных данных:
В первой строке содержатся числа n и k (0≤k≤n−1) - количество вершин и максимальное количество вершин которое можно удалить.В следующих n−1 строках следует описание графа.
В каждой строке содержатся числа u и v (1≤u,v≤n) - означает что существует неориентированное ребро между вершиной u и вершиной v.
Формат выходных данных:
Выведите ровно одно число - минимальный диаметр который можно получить удалив не более k вершин.Примеры:
1.Вход:5 2 1 4 3 2 1 2 5 2Ответ:
22.Вход:
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≤20
- 10 тестов: n≤100
- 5 тестов: k=0
- 24 тестов: n≤2000
- 51 тестов: n≤5000
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.