树

感受
被题解惊呆了，真没想到可以转化为DFS序，然后在链上思考这个问题！
学到了

思路
首先我们要明确染色策略，按照DFS序染***r>当我们染色到u点时，假如我们已经使用了k种颜色。
按照DFS序染色的规则，我们可以发现，u点的子树并没有被染色，相反u的的父亲，父亲的父亲,...，都一定被染色了，至于它的兄弟也可能被染色。
所以，我们考虑给u染色时，如果u染的颜色来自那k种，那么染的颜色一定与父亲相同，否则，肯定可以从u的非子树部分找到一个点，其颜色与u相同，这样的话，根据树的性质，u必须经过父亲才能到达那个点，这样就会产生冲突。
如果染非k的颜色话，可以随便染，一定不会冲突。
因此，DP转移式子
-

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300 + 10;
const ll mod = 1e9 + 7;
struct edge{
    int v, nex;
}e[maxn * 2];
int head[maxn], cnt;
int n, k;
ll dp[maxn][maxn];
void add_edge(int u, int v){
    cnt++;
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt;
}
int main(){
    scanf("%d%d", &n, &k);
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        //add_edge(u, v); add_edge(v, u);
    }
    dp[1][1] = k;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k && i >= j; j++){
            if(i == 1 && j == 1) continue;
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (k - j + 1);
            dp[i][j] %= mod;
            if(i == n) ans += dp[i][j], ans %= mod;
        }
    }
    printf("%lld\n", ans);
    return 0;
}