【每日一题】4.7树

原问题等价成，染色后，相同颜色在同一个连续的块内。
我们选取一个点作为根。
选用个颜色染色的方法，可以等价成：选取个点，选取个颜色，从下至上将每个点子树中未染色的点染上相应的颜色，且最后所有点都染上颜色。为了保证通过该方法使所有点染上颜色，根结点必选。
于是答案就是枚举颜色个数，然后从种颜色种选个颜色并分配，再从个点中选个点。将每次枚举的答案求和。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll fpow(ll a,ll n)
{
    ll sum=1,base=a;
    while(n!=0)
    {
        if(n%2)sum=sum*base%mod;
        base=base*base%mod;
        n/=2;
    }
    return sum;
}

ll inv(ll a)
{
    return fpow(a,mod-2);
}

ll jie[1005],rjie[1005];

void init()
{
    jie[0]=1;
    for(ll i=1;i<=1000;i++)jie[i]=jie[i-1]*i%mod;
    for(ll i=0;i<=1000;i++)rjie[i]=inv(jie[i]);
}

ll C(ll n,ll k)
{
    return jie[n]*rjie[k]%mod*rjie[n-k]%mod;
}

int main()
{
    init();
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
    }
    ll ans=0;
    for(int i=1;i<=k;i++)ans=(ans+C(n-1,i-1)*C(k,i)%mod*jie[i])%mod;
    printf("%lld\n",ans);
    return 0;
}