solution

仔细思考一下题意，发现其实就是要求将树分成不超过K个连通块，然后给每个连通块分配一种颜色。

假设连通块个数为x，那么根据乘法原理，给每个连通块分配不同颜色的方案数就是

然后问题就只剩下了如何求将树分成不超过K个连通块的方案数。

这显然可以用树形dp来求。

用f[u][i]表示将u这课子树划分为i个连通块的方案数。然后枚举一个u的子树v，同时枚举v子树中的连通块个数j。如果将v所在的连通块与u的颜色设为一样那么就会转移到，如果设为不一样，那么就会转移到。

这个dp过程的复杂度表面上是的，实际上是的。

只要在枚举连通块个数的时候，上限不超过子树大小即可。

原因我们可以考虑连边，也就是如果合并两个大小分别为s1和s2的子树，看做在这两棵子树每个点之间两两连边。显然，任意两个点之间最多会连1条边。所以总共最多会连条边。所以总复杂度就是

所以此题的数据范围其实还可以加强。

code

/*
* @Author: wxyww
* @Date: 2020-04-06 10:45:15
* @Last Modified time: 2020-04-06 10:58:24
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 310,mod = 1e9 + 7;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int f[N][N],siz[N],tmp[N];
void dfs(int u,int fa) {
    siz[u] = 1;
    f[u][1] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,u);

        memset(tmp,0,sizeof(tmp));
        for(int t1 = siz[u];t1 >= 1;--t1) {
            for(int t2 = siz[v];t2 >= 1;--t2) {
                tmp[t1 + t2] += 1ll * f[u][t1] * f[v][t2] % mod;
                tmp[t1 + t2] >= mod ? tmp[t1 + t2] -= mod : 0;
                tmp[t1 + t2 - 1] += 1ll * f[u][t1] * f[v][t2] % mod;
                tmp[t1 + t2 - 1] >= mod ? tmp[t1 + t2 - 1] -= mod : 0;
            }
        }
        siz[u] += siz[v];
        for(int j = 1;j <= siz[u];++j) f[u][j] = tmp[j];
    }
}
int jc[N];
int main() {
    int n = read(),K = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }
    jc[0] = 1;
    for(int i = 1;i <= K;++i) jc[i] = 1ll * jc[i - 1] * (K - i + 1) % mod;
    dfs(1,0);
    ll ans = 0;
    for(int i = 1;i <= K;++i) {
        ans += 1ll * f[1][i] * jc[i] % mod;
        ans >= mod ? ans -= mod : 0;
    }
    cout<<ans;

    return 0;
}