Выбор столицы
(Время: 5 сек. Память: 256 Мб Сложность: 73%)
Дано неориентированное дерево − связный граф из n вершин без циклов, и число k. Зафиксируем
некоторую вершину s дерева и назовем ее столицей.
Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро (u, v)
в направлении u → v, если при подвешивании дерева за вершину s вершина u является родителем
вершины v. Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы.
Определим расстояние до вершины v графа как минимальное количество ребер на пути из s в
v. Назовем доступностью вершины s максимальное из расстояний до всех вершин.
Разрешается добавить в дерево не более k дополнительных ориентированных ребер.
Для каждой вершины s дерева определите, какой минимальной доступности можно достичь,
если выбрать вершину s в качестве столицы.
Обратите внимание, что в некоторых подзадачах требуется вывести ответ только для первой
вершины.
Входные данные
Первая строка входного файла INPUT.TXT содержит три целых числа n, k и t (2 ≤ n ≤ 2×105, 1 ≤ k ≤ n-1, n×k ≤ 2×105, 0 ≤ t ≤ 1) − количество вершин дерева, ограничение на максимальное количество добавленных ребер и число t, равное 0, если нужно вывести ответ только для вершины с номером 1, и равное 1 иначе.
Каждая из следующих n-1 строк содержит два целых числа ui, vi (1 ≤ ui, vi ≤ n) − ребра дерева.
Гарантируется, что заданные ребра образуют дерево.
Выходные данные
В случае, если t = 0, в выходной файл OUTPUT.TXT выведите единственное целое число: минимальную доступность, которую
можно достичь, выбрав вершину с номером 1 в качестве столицы, и добавив не более k дополнительных ориентированных ребер.
В случае, если t = 1, выведите n чисел: i-е число равняется минимальной доступности, которую можно достичь, выбрав вершину i в качестве столицы, и добавив не более k дополнительных ориентированных ребер.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 2 1
1 2
1 3
2 4
2 5 | 1 1 2 2 2 |
| 2 | 3 1 0
1 2
2 3 | 1 |
Замечание
На рисунке приведены иллюстрации к первому примеру. Пунктирными линиями обозначены
добавленные ребра. Для вершин 1 и 2 минимальная доступность равняется 1, а для вершин 3, 4 и
5 минимальная доступность равняется 2.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
