【每日一题】树

首先思考一下，题目需要你将一棵树分成若干个连通块，连通块上的颜色相同，不同连通块之间的颜色不同。
然后数据范围很小，考虑树上dp，dp[i][j] 表示第 i 个节点为根的子树分成 j 个连通块的方案数。

然后我就不会了，但是仔细一想，把一棵树分成两个连通块不就是删除一条边，那分成 x 个连通块不就是选择 x-1 条边删除，然后在颜色里面选 x 种颜色给涂上去。这就是一个简单的组合数学问题。

如果把树分成 x 个连通块，那么就要选择 x-1 条边，也就是有 种方案，对于每一种分连通块的方案，可以有 种取颜色的方案，最后把颜色涂上去有 x 的全排列种也就是 种方案，那么把树分成 x 个连通块的答案 。而最终答案就是连通块个数 ，复杂度

其实这道题可以数据范围可以出到 的。

#include <bits/stdc++.h>
using namespace std;
static auto faster_iostream = []() { ios::sync_with_stdio(0); cin.tie(0); return 0; }();
typedef long long ll;
const int N = 1e3 + 5, M = 1e9 + 7;
ll qpow(ll x, ll n) { ll res = 1; for (; n; n >>= 1, x = x * x % M) if (n & 1) res = res * x % M; return res; }

ll fac[N];

ll comb(ll n, ll m) {
  return fac[n] * qpow(fac[m] * fac[n-m] % M, M - 2) % M;
}

int main() {
  int n, k;
  cin >> n >> k;

  fac[0] = fac[1] = 1;
  for (int i = 2; i <= max(n, k); i++) {
    fac[i] = fac[i-1] * i % M;
  }
  ll ans = 0;
  for (int i = 0; i <= min(n - 1, k - 1); i++) {
    ans += comb(n - 1, i) * comb(k, i + 1) % M * fac[i + 1] % M;
    ans %= M;
  }
  cout << ans << '\n';
}