Олимпиадный тренинг

Задача . F. Удаление мостов


Задача

Темы: Деревья дп жадные алгоритмы поиск в глубину и подобное сортировки Структуры данных *2800

Вам дано корневое дерево, состоящее из \(n\) вершин, пронумерованных от \(1\) до \(n\). Вершина \(1\) является корнем. Кроме того, у корня есть только один ребенок.

Требуется добавить ровно \(k\) рёбер в дерево (возможно, кратные рёбра и/или рёбра, уже существующие в дереве).

Напомним, что мост — это такое ребро, что после его удаления количество компонент связности в графе увеличивается. Таким образом, изначально все рёбра дерева являются мостами.

После добавления \(k\) рёбер некоторые изначальные рёбра дерева остаются мостами, а некоторые перестают ими быть. Необходимо удовлетворить два условия:

  • для каждого моста все рёбра дерева в поддереве нижней вершины этого моста также должны быть мостами;
  • количество мостов должно быть как можно меньше.

Решите задачу для всех значений \(k\) от \(1\) до \(n - 1\) и выведите наименьшее количество мостов.

Входные данные

В первой строке записано одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число \(n\) (\(2 \le n \le 3 \cdot 10^5\)) — количество вершин дерева.

В каждой из следующих \(n - 1\) строк записаны два целых числа \(v\) и \(u\) (\(1 \le v, u \le n\)) — описание рёбер дерева. Гарантируется, что заданные рёбра образуют валидное дерево.

Дополнительное ограничение на входные данные: корень (вершина \(1\)) имеет ровно одного ребенка.

Сумма \(n\) по всем наборам входных данных не превышает \(3 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите \(n - 1\) целое число. Для каждого \(k\) от \(1\) до \(n - 1\) выведите наименьшее количество мостов, которые могут остаться после добавления \(k\) рёбер в дерево.


Примеры
№Входные данныеВыходные данные
1 4
2
1 2
12
4 10
5 12
12 11
3 6
9 6
1 6
12 7
11 6
2 11
10 9
10 8
8
1 2
2 3
2 4
3 5
3 6
4 7
4 8
5
1 2
2 3
3 4
4 5 
0 
7 3 1 0 0 0 0 0 0 0 0 
4 1 0 0 0 0 0 
0 0 0 0

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет