思路：
这题我是看的这个题解然后加上自己的理解做出来的。
https://blog.nowcoder.net/n/a628960724c74b838b35f4c1d4b9617f
下面说一下我的理解:
一开始看的这个题，感觉不知道怎么搞，一开始想的是dfs暴力搞一下，但是要检查(u,v)颜色是不是相同就感觉写不出来。。。
然后看了一下题解是dp，定义
dp[i][j]:前i个节点从k种颜色中取j种颜色取染色的方案数。(一开始以为从前i个节点用j种颜色。。)
转移方程：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (k - (j - 1))
大概意思是：考虑第i个节点从k种颜色选j种的方案数会等于跟它父亲节点颜色保持一致(满足条件)，或者是用新的颜色那么就是原来父亲节点用了的颜色数量 * (总颜色数量 - 父亲节点用了的数量)这样相加就是dp[i][j]的数量了。

我感觉这题好像可以用组合数学的方法做，先想一想，想出来了再更新。
代码：

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

const long long int mod = 1000000000 + 7;
long long int  dp[10000][10000];
//dp[i][j]:前i个节点从k种颜色选择j种染树的方案数量 

void solved(){
    long long int n,k;cin>>n>>k;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (k - (j - 1));
            dp[i][j] %= mod;
        }
    }
    long long int ans = 0;
    for(int i = 1; i <= k; i++){
        ans += dp[n][i];
        ans %= mod;
    }
    cout<<ans;
}
int main(){
    solved();
    return 0;
}

组合数学做法：
我们可以从[1,k]枚举联通块的数量然后求出每种联通块能够染色方案数，因为方案数与顺序有关所以用排列，从一棵树中枚举联通块就是组合问题，然后乘法原理即可。
那么怎么枚举所有联通块呢？
假如有一个三个节点的树，我们知道联通块1数量 = 1，联通块2数量 = 3 ，联通块3数量 = 1.
每次多分割一个联通块就会多少一条边，分割i个联通块就会少 i - 1 条边，从边的角度去思考那么就是C(n - 1, i - 1)。然后用k种颜色去染i个联通块就是A(k,i)。
那么这题就出来了。答案就是图片说明
代码：

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

typedef long long int ll;
ll mod = 1e9 + 7;
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}

void solved(){
    ll n,k;cin>>n>>k;
    ll ans = 0;
    for(int i = 1; i <= k; i++){
        ans += (C(n - 1, i - 1)%mod * A(k,i,mod) % mod)%mod;
    }
    cout<<ans % mod<<endl;
}
int main(){
    solved();
    return 0;
}