E. Фиолетовый мелок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два игрока, Красный и Синий, снова в деле, и этот раз они играют с цветными мелками! Сегодня озорной паре под руку попалось корневое дерево, с которым они играют в свою любимую игру, раскрашивая вершины этого дерева.

Игра выглядит следующим образом: есть дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$, и каждая вершина первоначально белого цвета. У Красного и Синего есть ровно по одному ходу. Первым ходит Красный.

В свой ход, Красный может выполнить следующее действие произвольное количество раз:

  • Он выбирает любое поддерево корневого дерева и красит каждую из вершин поддерева в красный.
Однако, для большей честности, Красный может покрасить только $$$k$$$ вершин дерева. Другими словами, после окончания хода Красного, не более $$$k$$$ вершин может быть покрашено в красный.

Далее подходит очередь Синего. Он может выполнять следующее действие произвольное количество раз:

  • Он выбирает любое поддерево корневого дерева и красит каждую вершину поддерева в синий. Однако, ему нельзя выбирать поддеревья, в которых содержатся вершины, уже покрашенные в красный. Ведь в таком случае вершина получится фиолетового цвета, а никто не любит фиолетовый мелок* (англ. purple crayon).
Заметим, что нет ограничения на то, сколько вершин покрасит Синий, главное, что он не красит уже покрашенные Красным вершины.

После того как каждый сделает свой ход, счет игры определяется следующим образом: пусть $$$w$$$ — количество оставшихся белых вершин, $$$r$$$ — количество красных вершин, а $$$b$$$ — количество синих вершин. Счет игры будет равен $$$w \cdot (r - b)$$$.

Красный хочет максимизировать счет, а Синий — минимизировать. Чему будет равен счет игры, если оба игрока действуют оптимально?

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

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — количество вершин в дереве и максимальное количество красных вершин.

В следующих $$$n - 1$$$ строках заданы описания ребер дерева. В $$$i$$$-й строке заданы два целых числа $$$u_i$$$ и $$$v_i$$$ через пробел ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — $$$i$$$-е ребро дерева.

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

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

Выведите одно число — итоговый счет игры, если и Красный и Синий действуют оптимально.

Примеры
Входные данные
4 2
1 2
1 3
1 4
Выходные данные
1
Входные данные
5 2
1 2
2 3
3 4
4 5
Выходные данные
6
Входные данные
7 2
1 2
1 3
4 2
3 5
6 3
6 7
Выходные данные
4
Входные данные
4 1
1 2
1 3
1 4
Выходные данные
-1
Примечание

В первом наборе входных данных, одна из оптимальных стратегий следующая:

  • Красный выбирает для покраски поддеревья вершин $$$2$$$ и $$$3$$$.
  • Синий выбирает для покраски поддерево вершины $$$4$$$.
В результате вершины $$$2$$$ и $$$3$$$ покрашены в красный, $$$4$$$ — в синий, а вершина $$$1$$$ — в белый. Счет игры равен $$$1 \cdot (2 - 1) = 1$$$.

Во втором наборе, оптимальная стратегия следующая:

  • Красный выбирает для покраски поддерево вершины $$$4$$$. Тем самым красит вершины $$$4$$$ и $$$5$$$.
  • Синий не может ничего выбрать, а потому ничего не красит.
В результате вершины $$$4$$$ и $$$5$$$ покрашены в красный, а вершины $$$1$$$, $$$2$$$ и $$$3$$$ — белые. Счет игры равен $$$3 \cdot (2 - 0) = 6$$$.

В третьем наборе:

Счет игры равен $$$4 \cdot (2 - 1) = 4$$$.