树

分析：

这个题用到了树的以下性质：
如果两个节点位于同一个节点的两个不同子树上，那么这连接两个点的最短路径一定经过这个节点。
根据这个性质，很显然在树中新加入一个点时，只有两种情况

1. 使用一种新的颜色
2. 使用和相连的点相同的颜色

设f[i][j]表示前i个点使用j种颜色涂色的方案数
于是就有了转移方程：

   f[i][j]=f[i-1][j]+f[i-1][j-1]*(k-(j-1))

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> P;
const int INF=0x3f3f3f3f;
const LL LINF=0x3f3f3f3f3f3f;
const int MAX_N=320;
const LL MOD=1e9+7;
int n,k;
LL f[MAX_N][MAX_N];
int main(){
    //freopen("1.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    int x,y;
    for(int i=1;i<n;i++){
        cin>>x>>y;
    }
    dfs(1);
    LL ans=0;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            f[i][j]=(f[i-1][j]+f[i-1][j-1]*(k-(j-1))%MOD)%MOD;
        }
    }
    for(int i=1;i<=k;i++)   ans=(ans+f[n][i])%MOD;
    cout<<ans<<endl;
}