| Codeforces Round 936 (Div. 2) |
|---|
| Закончено |
Вам дано дерево из $$$n$$$ вершин.
Ваша задача — найти такое максимальное число $$$x$$$, что можно удалить из этого дерева ровно $$$k$$$ ребер так, чтобы размер каждой оставшейся компоненты связности$$$^{\dagger}$$$ был не менее $$$x$$$.
$$$^{\dagger}$$$ Две вершины $$$v$$$ и $$$u$$$ находятся в одной компоненте связности, если существует такая последовательность чисел $$$t_1, t_2, \ldots, t_k$$$ произвольной длины $$$k$$$, такая что $$$t_1 = v$$$, $$$t_k = u$$$, и для каждого $$$i$$$ от $$$1$$$ до $$$k - 1$$$ вершины $$$t_i$$$ и $$$t_{i+1}$$$ соединены ребром.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k < n \le 10^5$$$) — количество вершин в дереве и количество ребер, которое нужно удалить.
Каждая из следующих $$$n - 1$$$ строк каждого набора входных данных содержит два целых числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le n$$$) — очередное ребро дерева.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных в отдельной строке выведите такое максимальное число $$$x$$$, что можно удалить ровно $$$k$$$ ребер дерева так, чтобы размер каждой оставшейся компоненты связности был равен не менее $$$x$$$.
65 11 21 33 43 52 11 26 11 22 33 44 55 63 11 21 38 21 21 32 42 53 63 73 86 21 22 31 44 55 6
2 1 3 1 1 2
Дерево в первом наборе входных данных:
После удаления ребра $$$1$$$ — $$$3$$$ дерево будет выглядеть следующим образом:
Дерево распалось на две компоненты связности. Первая компонента состоит из двух вершин: $$$1$$$ и $$$2$$$. Вторая компонента связности состоит из трех вершин: $$$3, 4$$$ и $$$5$$$. В обоих компонентах связности не менее двух вершин. Можно показать, что ответ $$$3$$$ не достижим, поэтому ответ $$$2$$$.
