题目描述

• shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。
• 无序列表内容

  输入描述:

• 第一行两个整数n，k代表点数和颜色数；
• 接下来n-1行，每行两个整数x,y表示x与y之间存在一条边；
• 无序列表内容

  输出描述:

• 输出一个整数表示方案数（mod 1e9+7）。

解题思路：

小问好你是不是有很多朋友？是不是被标题树字带去直接开了个vector存结点信息了？ NONONO，这题其实可以使用动态规划去求解。
我们可以发现，x-y颜色要一样，说明树上全部相邻的点，要么颜色一样，要么颜色不一样。我们可以通过这个找到状态转移方程，我们通过dp[i][j] 代表存在i个点使用j种颜色的方法数，那么如果新加入一个点颜色和前面i-1个点颜色相同，直接方法数相加，如果和前面i-1个点颜色不同，那就要从(k-(j-1))种颜色选取一种没有被使用过的颜色，最后把n个点取1-k种方法数累加求和就是答案。
所以状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(k-j+1)

// 我跑的程序

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43371091&returnHomeType=1&uid=919749006

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 305;
const int MOD = 1e9 + 7;

ll dp[N][N]; // dp[i][j]表示i个点用j种颜色涂法

int main() {
    int n = read(), k = read();
    for (int i = 1; i < n; ++i)    int a = read(), b = read();
    for (int i = 1; i <= n; ++i)    dp[i][1] = k;
    for (int i = 1; i <= n; ++i)
        for (int j = 2; 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 += dp[n][i]) %= MOD;
    printf("%lld\n", ans);
    return 0;
}