这是绿？？？

首先不难发现，对于所有点集，我们都可以找到一个确定的点满足是这 kk 个点的 LCA，并且这 kk 个点满足在这个 LCA 的不同儿子的子树里，且深度相同。

发现 nn 和 kk 小的可怜，于是我们考虑动态规划，每次确定 LCA 和一个深度，令 dpi,jdp_{i,j} 为前 ii 个子树中有 jj 个子树里放了点的答案，对于第 ii 个儿子的就是 dpi,j=dpi−1,j+dpi−1,j−1×cnti,ddp_{i,j} = dp_{i - 1,j}+dp_{i-1,j-1}\times cnt_{i,d}，这里 cnti,dcnt_{i,d} 意思就是以 ii 为根节点的时候深度为 dd 的点个数，这里需要预处理，dd 是我们前面确定的一个深度。

然后做完了。

小心常数太大会 TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int>> edges(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    if (k == 2) {
        cout << (n * (n - 1) / 2) % mod << '\n';
        return;
    }
    int ans = 0;
    vector<vector<int>> cnt(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    for (int i = 1; i <= n; ++i) {
        cnt.assign(n + 1, vector<int>(n + 1, 0));
        function<void(int, int, int)> dfs = [&](int x, int fa, int dep) -> void {
            cnt[x][dep] = 1;
            for (auto nex : edges[x]) {
                if (nex == fa) {
                    continue;
                }
                dfs(nex, x, dep + 1);
                for (int j = 1; j <= n; ++j) {
                    cnt[x][j] += cnt[nex][j];
                }
            }
        };
        dfs(i, i, 1);
        for (int j = 1; j <= n; ++j) {
            dp.assign(n + 1, vector<int>(k + 1, 0));
            dp[0][0] = 1;
            for (int l = 1; l <= edges[i].size(); ++l) {
                dp[l][0] = 1;
                for (int m = 1; m <= k; ++m) {
                    dp[l][m] = (dp[l - 1][m] + dp[l - 1][m - 1] * cnt[edges[i][l - 1]][j] % mod) % mod;
                }
            }
            ans = (ans + dp[edges[i].size()][k]) % mod;
        }
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}