На день рождения юному Феде подарили дерево из $$$n$$$ вершин и бензопилу. Он хочет вырезать из него связанный подграф. Федя решил действовать следующим образом: он выбирает три различные вершины $$$a, b, c$$$ ($$$a \lt b \lt c$$$) и вырезает минимальный связный подграф, содержащий все три вершины. При этом он хочет, чтобы размер получившегося подграфа был ровно $$$d$$$ (то есть число вершин в вырезанном подграфе должно быть равно $$$d$$$).
Ему стало интересно, сколько различных таких подграфов он сможет вырезать. Подграфы называются различными, если выбранные тройки вершин не совпадают. Помогите ему справиться с этой задачей!
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержатся два числа $$$n$$$ и $$$d$$$ ($$$3 \le d \leq n \le 2000$$$) — число вершин в дереве и желаемый размер вырезанного подграфа.
Затем следуют $$$n - 1$$$ строка, в каждой из которых заданы два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), означающие вершины, соединённые очередным ребром. Гарантируется, что данный граф является деревом.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.
Для каждого набора входных данных выведите единственное число — количество различных подграфов, которые может вырезать Федя.
34 31 23 14 15 51 22 42 35 17 71 21 32 42 53 63 7
310
Так выглядит дерево для первого набора входных данных:
Подходят следующие тройки: ($$$1, 2, 3$$$), ($$$1, 2, 4$$$), ($$$1, 3, 4$$$). А для тройки ($$$2, 3, 4$$$) размер связанного подграфа будет равен $$$4$$$.
Так выглядит дерево для второго набора входных данных:
И для него подходит только тройка вершин ($$$3, 4, 5$$$).
Так выглядит дерево для третьего набора входных данных:
Можно показать, что для данного подграфа не подходит ни одна тройка.
| Codeforces Round 1099 (Div. 2) |
|---|
| Закончено |
