Solution

其实是道数论题。

题意可以转化为将树分割为不超过 个连通块，每个连通块颜色不同。若将树分割为 个连通块，则需要删去 条边，故方案数为 。同时，要从 种颜色中选出 中颜色染色，而且是有顺序的，故方案数为 。

综上，总的方案数为：

可以线性求逆元，枚举 实现。

时间复杂度： 。

Code

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const ll maxn=310;
ll n,k,ans,inv[maxn],f[maxn];
ll C(ll x,ll y){
    return f[x]*inv[y]%mod*inv[x-y]%mod;
}
ll A(ll x,ll y){
    return f[x]*inv[x-y]%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    inv[0]=f[0]=inv[1]=f[1]=1;
    for(ll i=2;i<maxn;i++)
        inv[i]=((mod-mod/i)*inv[mod%i])%mod,f[i]=i;
    for(ll i=2;i<maxn;i++)
        inv[i]=(inv[i]*inv[i-1])%mod,f[i]=(f[i]*f[i-1])%mod;
    for(ll i=1;i<=k&&i<=n;i++)
        ans=(ans+(C(n-1,i-1)*A(k,i)%mod))%mod;
    cout<<ans;
    return 0;
}