F. Дерево, ДЕРЕВО!!!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Корни меняются, но дерево стоит прочно — так же должно стоять и ваше логическое мышление.

Behruzbek получил дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин. Для выбранного корня$$$^{\text{†}}$$$ $$$r$$$ Behruzbek хочет найти привлекательность дерева.

Рассмотрим каждое множество из $$$k$$$ различных вершин дерева. Для каждого такого множества вычислите его наименьшего общего предка (LCA) в дереве, если дерево считать корневым в вершине $$$r$$$. Пусть $$$S_r$$$ — множество всех различных вершин, получающихся таким образом. Тогда привлекательность дерева является $$$|S_r|$$$, где $$$|S|$$$ означает количество различных чисел.

После того как Behruzbek узнал о привлекательности деревьев, Behruzbek заинтересовался нахождением кавайности дерева! Кавайность определяется как:

$$$$$$ \sum_{r = 1}^{n} |S_r| = |S_1| + |S_2| + \dots + |S_n| $$$$$$

К сожалению, Behruzbek сейчас чувствует себя сонным. Пожалуйста, помогите Behruzbek, найдя кавайность дерева!

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\text{†}}$$$Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем.

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

Первая строка содержит число $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq k \leq n \leq 2\cdot 10^{5}$$$) — число вершин в дереве и количество различных целых чисел, которые нужно выбрать.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^{5}$$$.

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

Для каждого набора входных данных выведите одно целое число — значение $$$\sum\limits_{r=1}^n |S_r|$$$.

Пример
Входные данные
4
2 2
1 2
5 3
1 2
1 3
1 4
1 5
6 3
1 2
1 3
2 4
2 5
3 6
10 5
5 6
4 9
3 9
2 6
2 8
8 9
6 10
1 6
4 7
Выходные данные
2
9
17
35
Примечание

Допустим $$$f(i) = |S_i|$$$

Для третьего набора входных данных:

  • Корень — $$$1$$$, можно получить только вершины $$$1$$$ и $$$2$$$. Например, можно выбрать: $$$LCA(4, 5, 6) = 1$$$ и $$$LCA(2, 4, 5) = 2$$$. В результате $$$f(1) = 2$$$.
  • Корень — $$$2$$$, можно получить только вершины $$$1$$$ и $$$2$$$. Например, можно выбрать: $$$LCA(1, 3, 6) = 1$$$ и $$$LCA(1, 4, 5) = 2$$$. В результате $$$f(2) = 2$$$.
  • Корень — $$$3$$$, $$$f(3) = 3$$$. Например, вершину $$$3$$$ можно получить, выбрав: $$$LCA(2, 4, 6) = 3$$$.
  • Корень — $$$4$$$, $$$f(4) = 3$$$. Например, вершину $$$2$$$ можно получить, выбрав: $$$LCA(1, 3, 5) = 2$$$.
  • Корень — $$$5$$$, $$$f(5) = 3$$$. Например, вершину $$$2$$$ можно получить, выбрав: $$$LCA(3, 4, 6) = 2$$$.
  • Корень — $$$6$$$, $$$f(6) = 4$$$. Например, вершину $$$3$$$ можно получить, выбрав: $$$LCA(3, 4, 5) = 2$$$.

В сумме получается $$$2 + 2 + 3 + 3 + 3 + 4 = 17$$$.