【每日一题】树 题解

Solution

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6  + 5;
const ll mod = 1e9 + 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll dp[305][305]; // dp[i][j]  i 个点用了 j 个色
vector<int> G[305];
int main(){
  int n, k;
  cin >> n >> k;
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    dp[i][1] = k; // 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; // 要么颜色相同, 要么从剩下的k - (j - 1) 种颜色里选一种新的
    }
  }
  for(int i = 1; i <= k; i++){
    ans += dp[n][i];
    ans %= mod;
  }
  cout << ans << "\n";
  return 0;
}