CF1551F题解

· · 题解

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;
}