[dp,prufer序列]CF917D Stranger Trees

\(\texttt{link}\)

有一个经典结论： 对于一个包含 \(n\) 个点的无向图，若连通块个数为 \(k\) ，大小分别为 \(s_1,...,s_k\)，则用 \(k-1\) 条边将 \(k\) 个连通块连起来的方案数为 \(n^{k-2}\prod\limits_{i=1}^k s_i\)。

记 \(dp(i,j,k)\) 表示子树 \(i\) 分成 \(j\) 个连通块，点 \(i\) 所在连通块大小为 \(k\) 的方案数，类似树上背包合并可以做到 \(\mathrm{O(n^3)}\)，但是可以做到更优。

考虑一个转化：\(\prod\limits_{i=1}^ks_i\) 等价于在每个块中选一个点的方案数。

于是可以设 \(dp(i,j,0/1)\) 表示子树 \(i\) 分成 \(j\) 个连通块，点 \(i\) 所在连通块是否选了一个点的方案数，类似树上背包合并就可以做到 \(\mathrm{O(n^2)}\) 了。

计算答案二项式反演即可。

\(\texttt{Code:}\)

#include 
#define pb push_back
#define fi first
#define se second

using namespace std;

const int cmd = 1e9 + 7;
const int N = 8e3 + 5;

int fpow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % cmd)
        if (b & 1) res = 1ll * res * a % cmd;
    return res;
}

int add(int a, int b) {a += b; return a < cmd ? a : a - cmd;}

int sub(int a, int b) {a -= b; return a < 0 ? a + cmd : a;}

int n, sb[N][2], fac[N], ifac[N], s[N], pw[N];

vector g[N];

vector dp[N][2];

void dfs(int u, int fa) {
    s[u] = 1;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) continue;
        dfs(v, u);
        s[u] += s[v];
    }
    dp[u][0].resize(s[u] + 1);
    dp[u][1].resize(s[u] + 1);
    dp[u][0][1] = dp[u][1][1] = 1;
    s[u] = 1;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) continue;
        for (int i = 1; i <= s[u] + s[v]; i++) sb[i][0] = sb[i][1] = 0;
        for (int i = 1; i <= s[u]; i++)
        for (int j = 1; j <= s[v]; j++) {
            sb[i + j][0] = add(sb[i + j][0], 1ll * dp[u][0][i] * dp[v][1][j] % cmd);
            sb[i + j][1] = add(sb[i + j][1], 1ll * dp[u][1][i] * dp[v][1][j] % cmd);
            sb[i + j - 1][0] = add(sb[i + j - 1][0], 1ll * dp[u][0][i] * dp[v][0][j] % cmd);
            sb[i + j - 1][1] = add(sb[i + j - 1][1], (1ll * dp[u][1][i] * dp[v][0][j] + 1ll * dp[u][0][i] * dp[v][1][j]) % cmd);
        }
        for (int i = 1; i <= s[u] + s[v]; i++)
            dp[u][0][i] = sb[i][0], dp[u][1][i] = sb[i][1];
        s[u] += s[v];
    }
}

int C(int n, int m) {
    return 1ll * fac[n] * ifac[m] % cmd * ifac[n - m] % cmd;
}

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d", &n);
    if (n == 1) {puts("1"); return 0;}
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1, 0);
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = 1ll * fac[i - 1] * i % cmd;
        ifac[i] = fpow(fac[i], cmd - 2);
    }
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = 1ll * pw[i - 1] * n % cmd;
    for (int i = 0; i < n; i++) {
        int ans = 0;
        for (int j = i; j < n; j++) {
            int cur;
            if (n - j == 1) cur = C(j, i);
                else cur = 1ll * C(j, i) * dp[1][1][n - j] % cmd * pw[n - j - 2] % cmd;
            if ((j - i) & 1) ans = sub(ans, cur);
                else ans = add(ans, cur);
        }
        printf("%d ", ans);
    }
    return 0;
}