← 返回题目列表

Codeforces · 1551/F

F. 等距顶点

中文机器翻译题面 查看原题

树是没有环的无向连通图。

给你一棵有 $$$n$$$ 个顶点的树。找到在这棵树中精确选择 $$$k$$$ 顶点(即 $$$k$$$ 顶点的元素子集)的方法数量,以便所选顶点之间的所有成对距离都相等(换句话说,存在一个整数 $$$c$$$,使得对于所有 $$$u, v$$$ ($$$u \ne v$$$, $$$u, v$$$ 都在所选中顶点)$$$d_{u,v}=c$$$,其中 $$$d_{u,v}$$$ 是从 $$$u$$$ 到 $$$v$$$ 的距离)。

由于答案可能非常大,因此需要对 $$$10^9 + 7$$$ 进行模输出。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例前面都有一个空行。

每个测试用例由几行组成。测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 100$$$) — 分别是树中的顶点数和要选择的顶点数。然后是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),它们描述由边连接的一对顶点。保证给定的图是一棵树并且没有循环或多重边。

输出

对于每个测试用例,在单独的行中输出一个整数 - 精确选择 $$$k$$$ 顶点的方法数量,以便对于所有选定的顶点对,各对顶点之间的距离相等,以 $$$10^9 + 7$$$ 为模(换句话说,打印除以 $$$1000000007$$$ 后的余数)。

示例

输入 #1

3

4 2
1 2
2 3
2 4

3 3
1 2
2 3

5 3
1 2
2 3
2 4
4 5

输出 #1

6
0
1