[每日一题]4.7 树

题意：给出一颗树，有个节点，用种不同的颜色给每个节点染色，要求保证所有相同颜色的节点都相邻

设计知识点：排列组合

解法：首先，题意可以理解为将其分成 个联通分量的染色方案数之和，将一棵树拆分成 i 个联通分量需要砍掉条边，就相当于从条边选择条边，那么方案数就是,接下来就可以从个颜色中选择种颜色，方案数就是,所以我们只需要先预处理一下组合数，然后枚举一下，累加到答案即可

时间复杂度：

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int maxx = 405;
ll fm[maxx],fz[maxx];
ll pow_mod(ll a,ll b){
  ll ans = 1;
  while(b){
      if(b&1)
         ans = ans*a%mod;
      a = a*a%mod;
      b>>=1;
  }
  return ans;
}
void init(){
  fm[0] = 1;
  fz[0] = 1;
  for(int i=1;i<=305;i++){
      fm[i] = fm[i-1]*i%mod;
      fz[i] = pow_mod(fm[i],mod-2)%mod;
  }
  return ;
}
ll C(ll x,ll y){
  return fm[x]*fz[y]%mod*fz[x-y]%mod;
}
ll A(ll x,ll y){
  return fm[x]*fz[x-y]%mod;
}
int main()
{
  ll n , k, ans = 0;
  int x, y;
  cin>>n>>k;
  for(int i=1;i<n;i++)cin>>x>>y;
  init();
  for(int i=1;i<=min(n,k);i++)
      ans += (C(n-1,i-1)%mod*A(k,i))%mod , ans%=mod;
  cout<<ans<<endl;
  return 0;
}