牛客 - 树

传送门：牛客 - 树

思路分析

既然是一棵树，题意可以转化为最多给K个连通块染色，求方案数
从叶子节点除法，用$dp[i][j]$表示前i个节点，用j种颜色染色的方案数

样例输入

4 3
1 2
2 3
2 4

样例输出

39

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N=333;

ll dp[N][N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    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)))%mod;
    
    ll ans=0;
    for(int i=1;i<=k;i++) ans=(ans+dp[n][i])%mod;
    cout<<ans<<endl;





    return 0;
}