【每日一题】树 (dp)

Solution
因为是树，所以保证任意两点都可以到达，所以可以选择从一个叶子节点作为出发点思考，

表示这个叶子节点所在包含了 i 个节点的子图染了 j 种颜色的方案。
考虑当前取的颜色是否和前 次取的颜色一样，就是两种决策：

1. 若取的颜色相同则：
2. 若取的是新的颜色,则有 种新颜色可以选择，则：

这样的话就可以从一个叶子节点开始染色到把整棵树染色。
最后累加 n 个点取 1~k 种颜色的方案即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }

const int manx=3e2+5;

ll mod=1000000000+7;

ll dp[manx][manx];

int main(){
    ll n=read(),k=read();
    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)+dp[i-1][j]), dp[i][j]%=mod;
    ll ans=0;
    for(int i=1;i<=k;i++)
        ans+=dp[n][i],ans%=mod;
    cout<<ans;
    return 0;
}