【每日一题】树

题目要求对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。
相当于切掉树上的 x 条边（0<= x <= min(n-1,k-1)），让原树变成x+1个连通块，每个连通块涂成一个颜色，问有多少种方案；
ans =
C(n-1,i)是从n-1条边选i条边切，分成i+1个连通块，再在k种颜色内选i+1种给i+1个连通块上***r>预处理求下组合数，P(n,m)用C(n,m)*m!求得

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int N = 305;
ll c[N][N],fac[N];
void init(){
    //c[a][b]，组合数 
    for(int i = 0;i < N;i++){
        for(int j = 0;j <= i;j++){
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
    //fac[n],阶乘
    fac[0] = 1;
    for(int i = 1;i < N;i++){
        fac[i] = (fac[i-1]*i)%mod;
    } 
}
int n,k;
int main(){
    init();
    while(~scanf("%d%d",&n,&k)){
        for(int i = 1;i < n;i++){
            int u,v;scanf("%d%d",&u,&v);
        }
        ll res = 0;
        for(int i = 0;i <= min(n-1,k-1);i++){
            res+=((c[n-1][i]%mod*c[k][i+1]%mod)%mod*fac[i+1])%mod;
            res%=mod;
        }
        printf("%lld\n",res);
    }
    return 0;
}