本想着 Div.3 玩玩就好，所以直接开了最后一题，想着 \(40\) 分钟内可以解决。然后就……悲剧了。
对借给我帐号的选手表示诚挚的歉意。
给定一棵 \(n\) 个节点的树，求选出 \(k\) 个点，它们两两距离相同的方案数。
首先容易发现一个性质，如果 \(k > 2\)，那么这些点一定有一个“中心点”本身不被选中但所有选中的点到它距离都一样。
那么考虑枚举这一个中心点，以其为根把树变成有根树，考虑每一个距离求方案数。但这样还不行，因为如果有俩点的 LCA 不是根，那么它们之间的距离就和到其它点之间的距离不一样了。
所以还必须要 LCA 是根。那么就是要每个子树中最多只能选一个点。
现在想想方案怎么计数。
一开始想的是可能存在神奇的组合数方法，但想了一会儿未果，而且数据范围那么小，似乎并不是想让我们去推式子组合数的。所以考虑 dp。
\(f_{i, j}\) 表示根的前 \(i\) 个子树中一共有 \(j\) 个子树中取了点的方案数。那么转移就两种，当前子树取点或不取点，易得 \(f_{i, j} = f_{i-1,j} + f_{i-1, j-1} \times a_i\)，其中 \(a_i\) 是第 \(i\) 棵子树的该层点数。
那么做法就很清晰了。
- 枚举一个根。
- dfs 记录每个子树下面每一个深度的点数。
- 枚举每一个深度。
- 进行 dp。
不要忘了好好地清空数组！我因为清空时写了：
for (int j = 1; j <= n; j++)
for (int l = 0; l <= n; l++) num[i][j] = 0;
调了一个小时 qwq。
点击查看完整代码
#include <iostream>
#include <vector>
#define int long long
const int N = 205, P = 1000000007;
int T, n, k, x, y, num[N][N], f[N][N];
std::vector<int> g[N];
std::vector<int> a;
void dfs(int u, int fa) {
num[u][0] = 1;
for (int i = 0; i < (int)g[u].size(); i++) {
int v = g[u][i];
if (v == fa) continue;
dfs(v, u);
for (int j = 1; j <= n; j++)
num[u][j] += num[v][j-1];
}
}
signed main() {
std::cin >> T;
while (T--) {
std::cin >> n >> k;
int ans = 0;
for (int i = 1; i < n; i++)
std::cin >> x >> y, g[x].push_back(y), g[y].push_back(x);
if (k == 2) {
std::cout << n * (n-1) / 2 << ‘\n‘;
for (int i = 1; i <= n; i++) g[i].clear();
continue;
}
for (int i = 1; i <= n; i++) {
dfs(i, 0);
for (int j = 1; j <= n; j++) {
for (int l = 0; l < (int)g[i].size(); l++)
a.push_back(num[g[i][l]][j-1]);
f[0][0] = 1;
for (int x = 1; x <= (int)a.size(); x++) {
f[x][0] = 1;
for (int y = 1; y <= x; y++)
f[x][y] = (f[x-1][y] + f[x-1][y-1]*a[x-1]%P) % P;
}
ans = (ans + f[a.size()][k]) % P;
for (int x = 1; x <= (int)a.size(); x++)
for (int y = 1; y <= x; y++) f[x][y] = 0;
a.clear();
}
for (int j = 1; j <= n; j++)
for (int l = 0; l <= n; l++) num[j][l] = 0;
}
std::cout << ans << ‘\n‘;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++) num[i][j] = 0;
}
return 0;
}
感觉这题充其量就 \(1900\)，居然让我调了那么久，看样子以后 Div.3 还是有必要练习的。