【每日一题】树 (dp)

Solution
任意颜色相同的点对，中间的颜色也相同，那么意思就是同一种颜色必须形成联通块。
dp[i][j]表示前i个点染了j种颜色的方案数，那么当前状态要么和以前染过颜色一样,即dp[i][j]+=dp[i-1][j];要么不一样，那就是从剩下的k-j+1种里面选，即dp[i][j]+=dp[i-1][j-1]*(k-j+1),两个式子整合一下就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n, k, res, dp[305][305];
int main() {
  cin >> n >> k;
  dp[0][0] = 1;
  for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= min(i, k); j++)
      dp[i][j] =
          (dp[i][j] + dp[i - 1][j] + dp[i - 1][j - 1] * (k - j + 1)) % mod;
  for (ll i = 1; i <= k; i++) res = (res + dp[n][i]) % mod;
  cout << res << '\n';
  return 0;
}