Минимальное количество зельда-операций, необходимых для того, чтобы в дереве осталась только одна вершина

Вчера был раунд на кодфорсес, вот одна из задача(прямая ссылка - https://codeforces.com/contest/1905/problem/B)
Вам дано дерево†. За одну зельда-операцию вы можете сделать следующее:

Выбрать две вершины дерева u и v;
Сжать все вершины на пути от u до v в одну вершину. Другими словами, все вершины на пути от u до v будут удалены из дерева, будет создана новая вершина w. Затем каждая вершина s, которая имела ребро с какой-то вершиной на пути от u до v, будет иметь ребро с вершиной w.
(поясняющая картинка - https://espresso.codeforces.co... 23236b.png)
Иллюстрация результата зельда-операции для вершин 1 и 5.
Определите минимальное количество зельда-операций, необходимых для того, чтобы в дереве осталась только одна вершина.

†Дерево — это неориентированный связный граф без циклов.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число t (1≤t≤104) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число n (2≤n≤10⁵) — количество вершин.

i-я из следующих n−1 строк содержит два целых числа u_i и v_i (1≤u_i,v_i≤n,u_i≠v_i) — номера вершин, соединенных i-м ребром.

Гарантируется, что заданные рёбра образуют дерево.

Гарантируется, что сумма n по всем наборам входных данных не превышает 10⁵.

Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество зельда-операций, необходимых для того, чтобы в дереве осталась только одна вершина.

Пример
входные данныеСкопировать
4
4
1 2
1 3
3 4
9
3 1
3 5
3 2
5 6
6 7
7 8
7 9
6 4
7
1 2
1 3
2 4
4 5
3 6
2 7
6
1 2
1 3
1 4
4 5
2 6
выходные данныеСкопировать
1
3
2
2
Примечание
В первом наборе входных данных достаточно выполнить одну зельда-операцию для вершин 2 и 4.

Во втором наборе входных данных мы можем выполнить следующие зельда-операции:

u=2,v=1. Пусть добавленная вершина будет обозначена как w=10;
u=4,v=9. Пусть добавленная вершина будет обозначена как w=11;
u=8,v=10. После этой операции дерево состоит из одной вершины.



Само решение задачи говорит, что ответ для любого из тестов = [(K+1)/2], где K - graph's leaves. Так вот, что за листья графа и почему это так работает? Есть ли другие решения задачи?

0

Сообщение от DOPIXKMNLD Есть ли другие решения задачи?

А где еще?
Одна операция уменьшает количество листьев не более чем на 2.

0

Red white socks, что такое листья графов? Вершиы/ребра?

0

DOPIXKMNLD, листья не у всякого графа, а у дерева.
Вас гуглом учить пользоваться?
Теорию графов в самом поверхностном виде (общие понятия) желательно изучить, и ме по подворотням на форумах , а желательно по нормальным учебникам. Их также полно.

Добавлено через 5 минут
В дереве вершины степени 1 называются листьями.

1