本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-26 13:50:14

CF Round #734(Div.3) F,Equidistant Vertices

题意：

洛谷题目链接

CF题目链接

给定一棵有 $n$ 个点的树，要求选出 $k$ 个点，使得这 $k$ 个点两两距离相同。

输入数据有 $t$ 组（ $1 \leq t \leq 10$ ），每组数据第一行有两个数 $n$ 和 $k$ （ $2 \leq k \leq n \leq 100$ ），意义如上，下面 n−1 n-1n−1 行每行有两个数 u,vu,vu,v 代表有一条边连接 u,vu,vu,v 两个点，对于每组数据，输出方案数，答案对 $10^9+7$ 取模。

题解思路：

我们先特判一下，当 $k \le 2$ 的时候，那么他们的距离是相同的。

当 $k=3$ 时，只有他是有分叉的，才有可能使得这三个点两两距离相同。那么他们的距离就是他们分叉的距离两两相同。

所以当 $k \ge 3$ 时，他们的结果是一样的。

还有一个隐含条件，就是这些点不在同一子树里。

那么组合数就不可做了。

而我们发现 $n$ 很小，所以我们可以枚举分叉点，我们就求他离分叉点有多远的点的个数。

我们设距离为 $d$，那么我们就统计离分叉点距离为 $d$ 的点的个数。

记为 $c_1,c_2,c_3,...,c_k$，其中 $k$ 是子树的个数。

那么我们设 $dp_{i,j}$ 表示前 $i$ 个分支，并选了 $j$ 个点。

那么状态转移方程为： $$dp_{i,j} = (dp_{i-1,j} + dp_{i-1,j-1} \times c_i)$$ 那么时间复杂度为 $\mathcal{O(n^2 k)}$。

并且我们还可以把 $i$ 这一维给优化掉。

因为这道题的范围很小，所以我们可以用floyd求最短路。

AC CODE：

#include <bits\/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 110;
int n, k, g[N][N];
int cnt[N], dp[N];
void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			g[i][j] = (i == j) ? 0 : mod;
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u][v] = g[v][u] = 1;
	}
	if (k == 2) {
		printf("%d\n", n * (n - 1) \/ 2);
		return;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int d = 1; d <= n; d++) {
			for (int j = 1; j <= n; j++)
				cnt[j] = 0;
			for (int u = 1; u <= n; u++)
				if (g[i][u] == d) {
					for (int v = 1; v <= n; v++)
						if (g[i][v] == 1 && g[i][u] == g[i][v] + g[v][u]) {
							cnt[v]++;
						}
				}
			for (int j = 1; j <= k; j++)
				dp[j] = 0;
			dp[0] = 1;
			for (int j = 1; j <= n; j++)
				if (cnt[j] > 0) {
					for (int l = k; l >= 1; l--)
						dp[l] = (dp[l] + 1ll * dp[l - 1] * cnt[j]) % mod;
				}
			ans = (ans + dp[k]) % mod;
		}
	}
	printf("%d\n", ans);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		solve();
	}
	return 0;
}