题目大意

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

解答

千万不要被树迷惑了，仔细一想，这和树有什么关系呢？
可以转换一下思路：题目的意思就是最多切k-1条边，切出来一些连通块，且联连通块里的所有边的颜色相同，所以答案就是
就是从(n-1)条边种选i条边切，然后从k种颜色给这i+1个点染色，然后求和，最后+k就是所有点染一个颜色，其实可以被归类到一条边都不切。
所以只要与处理一下C(n,m)就ok啦~

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 350, mod = 1e9+7;
int n,k;
ll fact[N];
ll C[N][N];

void init(){
    fact[1] = 1;
    for (int i = 2; i <= N; i ++){
        fact[i] = (i * fact[i-1]) % mod;
    }

    C[1][1] = 1;
    C[1][0] = 1;
    for (int i = 2; i <= N; i ++) C[i][0] = 1;

    for (int i = 2; i < 350; i ++)
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;

}

int main()
{
    init();
    cin >> n >> k;
    for (int i = 1; i <= n-1; i ++)
    {
        int a, b;
        cin >> a >> b;
    }
    int m = n-1;
    int cut = k-1;

    ll ans = 0;

    for (int i = 1; i<=cut && i <=m; i ++)
    {
        ans += (((C[m][i] * C[k][i+1])%mod) * fact[i+1]) % mod;
    }
    cout << (ans + k)%mod;
}