| Codeforces Round 975 (Div. 1) |
|---|
| Закончено |
Вам дано дерево с $$$n$$$ вершинами, корень которого находится в вершине $$$1$$$. В этой задаче лист — это некорневая вершина со степенью $$$1$$$.
За одну операцию можно удалить лист и смежное с ним ребро (возможно, появятся новые листья). Какое минимальное количество операций нужно выполнить, чтобы получилось дерево, также с корнем в вершине $$$1$$$, в котором все листья находятся на одинаковом расстоянии от корня?
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 5 \cdot 10^5$$$) — количество вершин.
Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$, $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), описывающих ребро, соединяющее $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число: минимальное количество операций, необходимое для достижения цели.
371 21 32 42 54 64 771 21 31 42 53 65 71512 91 66 149 118 73 513 56 1013 1513 614 127 28 11 4
2 2 5
В первых двух наборах входных данных деревья выглядят так:
В первом наборе входных данных, удалив ребра $$$(1, 3)$$$ и $$$(2, 5)$$$, вы получите дерево, у которого все листья (вершины $$$6$$$ и $$$7$$$) находятся на одинаковом расстоянии от корня (вершины $$$1$$$), которое равняется $$$3$$$. Ответ — $$$2$$$, так как это минимальное количество ребер, которое нужно удалить для достижения цели.
Во втором наборе входных данных удаление ребер $$$(1, 4)$$$ и $$$(5, 7)$$$ приводит к дереву, в котором все листья (вершины $$$4$$$ и $$$5$$$) находятся на одинаковом расстоянии от корня (вершины $$$1$$$), которое равняется $$$2$$$.
