【每日一题】树 dp

题意：给出n个结点的树用k种不同的颜色染色当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同个染色方案才是合法的

题意：既然是颗树连通性是一定的题目说的有点绕但其实就是至多给k个联通块染色求染色方案数从一个叶子结点出发
考虑用 $图片说明$ 来代表前i个结点染j种颜色的方案数

转移方程也很容易想到就是 $图片说明$
即染和前一个结点一样的颜色和染新的颜色除去前j-1种外还有 k - （j - 1）种最后把n个结点染色情况相加即可

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define mes(x,a) memset(x,a,sizeof(x));
#define sca(a) scanf("%d",&a)
#define lowbit(x)  x & (-x)
#define fi first
#define se second
#define pii pair<int, int>

inline int read()
{
    int x=0,flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*flag_read;
}

const double eps=1e-9;
const double pi=acos(-1);
const int N = 1e5 + 5;
const int M = 1e7+5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

LL dp[305][305];///前i个点染j种颜色的方案数

int main()
{
    int n = read();
    int 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] + (dp[i - 1][j - 1]*(k - (j - 1)));
            dp[i][j] %= mod;
        }
    }

    LL res = 0;

    for(int i = 1;i <= k;i ++)
        res = (res + dp[n][i])%mod;

    printf("%lld\n",res);

    return 0;
}

【每日一题】 树 dp

【每日一题】树 dp