每日一题 树

题意：
给树上联通块染色，染色颜色不超过k的方案数.
思路：
按照dfs序便利，用dp[i][j]代表考虑前i个的dfs序列涂j种颜色的方案数，初始状态，dp[1][1]=k,转移呢，dp[i][j]=dp[i-1][j-1]+（k-j+1)dp[i-1][j-1].为什么这么转移呢，一种是用新的颜色，另一种是用与他的父节点相同的颜色。

#include<bits/stdc++.h>
using namespace std;
const int N=310;
#define int long long 
const int mod=1e9+7;
int dp[N][N];
int n,k;
int dfn[N];
vector<int>v[N];
int idx;
void dfs(int u,int fa)
{
    dfn[u]=++idx;
    for(auto j:v[u])
    {
        if(j==fa)   continue;

        dfs(j,u);
    }
}
signed main()
{
    cin >> n >> k;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dp[1][1]=k;
    dfs(1,0);
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=(dp[i-1][j-1]*(k-j+1)+dp[i][j]+dp[i-1][j])%mod;

        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res=(res+dp[n][i])%mod;
    cout<<res<<endl;
    return 0;


}