dp做法

时间复杂度$O(nk)$。

在树中选择任意一个叶子结点作为起点，沿着边一个点接一个点的涂色。定义$dp[i][j]$为前$i$个点使用了$j$种颜色的方案数，状态转移方程：

• 若第$i$个点选用未使用的颜色，则$dp[i][j]+=dp[i-1][j-1]*(k-j+1)$。
• 若第$i$个点选用已经使用过的颜色，则必须和$i-1$的颜色相同，若和更前面的结点颜色相同则在路径中会经过$i-1$不符合题意，则$dp[i][j]+=dp[i-1][j]$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;

int n, k;
int u, v;
LL dp[377][377];
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++) scanf("%d%d", &u, &v);
    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;
        }
    }
    for(int j = 1; j <= k; j++) {
        dp[n][j] = (dp[n][j] + dp[n][j - 1]) % mod;
    }
    printf("%lld\n", dp[n][k]);
    return 0;
}

连通块做法

时间复杂度$O(nlog_{2}{n})$，下面代码中的逆元可以进一步优化。

问题转化为把一棵树分成多个连通块，每个连通块内的结点涂相同的颜色，不同的连通块颜色不同，有多少种方案。

• 若把$n$个结点的树分成$m$个连通块，则需要删除$m-1$条边，有$C_{n-1}^{m-1}$种方案。
• $k$种颜色需要选出$m$种，有$C_{k}^{m}$种方案。
• $m$种颜色涂$m$个连通块，有$m!$种方案。
• 上面三个条件满足乘法原理，则对答案的贡献为$C_{n-1}^{m-1}*C_{k}^{m}*m!$，最后只需要枚举一下可以分成多少个连通块求和即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;

int n, k;
int u, v;
LL fac[377], sum;
LL fast_pow(LL a, LL n) {
    LL ret = 1, temp = a % mod;
    while(n) {
        if(n & 1) ret = ret * temp % mod;
        temp = temp * temp % mod;
        n >>= 1;
    }
    return ret;
}
LL Comb(int n, int m) {
    return fac[n] * fast_pow(fac[m] * fac[n - m], mod - 2) % mod;
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++) scanf("%d%d", &u, &v);
    fac[0] = fac[1] = 1;
    for(int i = 2; i < 377; i++) fac[i] = fac[i - 1] * i % mod;
    if(k > n) k = n;
    for(int i = 1; i <= k; i++) {
        sum = (sum + Comb(n - 1, i - 1) * Comb(k, i) % mod * fac[i]) % mod;
    }
    printf("%lld\n", sum);
    return 0;
}

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/143/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。