Дерево коротких расстояний
Задано неориентированное дерево, состоящее из вершин. Неориентированное дерево — это связный граф с ребром.
Ваша задача — добавить минимальное количество ребер таким образом, чтобы длина кратчайшего пути из вершины до любой другой вершины не превышала . Заметьте, что Вы не можете добавлять петли и кратные ребра.
Giriş verilənləri
Первая строка содержит одно целое число — количество вершин в дереве.
Следующие строк описывают ребра: ребро задано как пара вершин . Гарантируется, что заданный граф является деревом. Гарантируется, что среди заданных ребер петли и кратные ребра отсутствуют.
Çıxış verilənləri
Выведите одно целое число — минимальное количество ребер, которое необходимо добавить, чтобы длина кратчайшего пути из вершины до любой другой вершины не превышает . Заметьте, что вы не можете добавлять петли и кратные ребра.