CF1551F Equidistant Vertices

一棵树是一个无环的连通无向图。 给定一棵有 $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$ 取模后的结果。

由 ChatGPT 4.1 翻译