题目描述

shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数

题解

太妙了太妙了，
1.首先既然任意相同颜色的点的路径均为一个颜色，那这其实就是当于一个联通块。
那么本题就转化为把这颗树划分为小于等于k的连通块，然后在这些颜色相同的连通块上任意染色就可以了。

2.所以我们可以枚举连通块的个数，然后用这棵树能划分成这些连通块的方案数*染色的排列组合就能得到答案

3.那现在的问题就是怎么求i个连通块的方案数？
由于这是一颗树，任意一条边都连接着两个连通块，那么将这颗树划分为i个连通块，其实就是相当于在这n-1条中选择i-1条边删掉，所以方案数就为C(n-1,i-1);

代码

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head
int n,k;
LL f[maxn];
LL C(int n,int m){
   if(m>n) return 0;
   return f[n]*inv(f[n-m])%mod*inv(f[m])%mod;
}
LL calu(int i){
   return C(n-1,i-1)*f[k]%mod*inv(f[k-i])%mod;
}
int main(){
    scanf("%d%d",&n,&k);
    f[0]=1;
    for(int i=1;i<=10000;i++){
        f[i]=f[i-1]*i%mod;
    }
    LL ans=0;
    for(int i=1;i<=k;i++){
        (ans+=calu(i))%=mod;
    }
    printf("%lld\n",ans);
}