【每日一题】树

思路：
我们知道树是联通的，即任意两点之间一定是可以到达的，那么题意等价
能将这棵树分成多少个联通块，并且最多只能分解k个联通块
那么其实这棵树的结构是怎么样的我们并不在乎
只需要考虑当前节点和上一个节点是不是要在同一个连通块即可
所以考虑dp
dp[i][j]表示前i个节点分成j个联通块的方案数
转移方程易得dp[i][j]=dp[i-1][j]+(k-(j-1))*dp[i-1][j-1]
即 要么第i个和第i-1个同一块 要么在剩下的k-(j-1)块中选一块
注意块和块是互不相同的 比如1在第一块 23在第二块 和1在第二块 23在第一块这是两种方案
边界的话就是dp[0][0]=1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[505][505];
int main(){
    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-1]*(k-j+1)%mod+dp[i-1][j])%mod;
        }
    }
    ll sum=0;
    for(int i=1;i<=k;i++) sum+=dp[n][i];
    cout<<sum%mod;

    return 0;
}