P9669 [ICPC2022 Jinan R] DFS Order 2 题解

· · 题解

萌萌树上 dp 题，不过细节有点多，还要注意常数。

Part 1 思路

看到这一类计数题，我们可以很直接的想到设 dp_{i,j} 为节点 i 的 dfs 序为 j 的方案数。但如果这样设计，容易发现很难从一个节点转移到其子结点。因此我们规定 dp_{i,j} 为节点 i 在不考虑其子树内部的情况下 dfs 序为 j 的方案数，则最终的答案矩阵 ans_{i,j} = dp_{i,j} \times w_i，其中 w_i 表示遍历 i 的子树的方案数。

较为简单的，设 size_u 表示 u 的子结点个数，则 w_u = size_u! \times \prod_{v \in son(u)} w_v。注意前面的系数来源于遍历子结点顺序不同。

接下来，我们发现从父节点 u 向子结点 v 转移需要一个权值矩阵 g_{i,j}。表示在不考虑先后顺序的前提下从 u 开始遍历再到开始遍历 v 所在的子树且中间恰好经过了 i 个不同的 u 的子结点所在的子树与 j 个不同的节点。换句话说，就是从 u 的子结点中选出 i 个不为 v 的点，其子树大小的和为 j 的方案数。这个明显可以用类似背包的方法做。那么从 u 到 v 经过节点数量为 x 的方案数为 now_x = \sum_{i = 1}^{size_u - 1} g_{i,x} \times (i - 1)! \times (size_u - i - 1)! \times \frac{w_u}{w_v \times size_u!}，(i - 1)! 与 (size_u - i - 1)! 的系数来源前后两部分的顺序任意，而 \frac{w_u}{w_v \times size_u!} 则来源于考虑 v 的兄弟节点内部顺序的贡献。同时注意特判 now_0 的情况。

最后我们发现，dp_{v, i} = \sum_{j = 1}^{i - 1}dp_{u, j} \times now_{i - j - 1}。但此时由于对每个节点都需要计算一次 g 与 now，这使得时间复杂度为 O(n^4)，这是无法接受的。因此需要提前计算对于每一个节点 u 所有的子结点所贡献的 g 与 now，然后再消去每一个节点的贡献。我是不会告诉你我一开始是不知道这叫回滚背包的。 最后就是 O(n^3) 的了。

Part 2 代码

注意数组要及时清空，转移系数要预处理同时取模可以优化。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 505;
const ll MOD = 998244353;
int n, cnt = 0, head[MAXN];
int f[MAXN][MAXN][MAXN], dp[MAXN][MAXN];
ll sum[MAXN], w[MAXN], S[MAXN], jc[MAXN], ans[MAXN][MAXN], now[MAXN];
struct edge {
    int to, next;
} e[MAXN << 1];
inline void add(int u, int v) {
    cnt++;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
inline ll qmi(ll a, ll b) {
    ll res = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * res % MOD;
        res = res * res % MOD;
        b >>= 1;
    }
    return ans;
}
inline void dfs(int u, int pre) {
    sum[u] = 1, w[u] = 1;
    for (int i = head[u]; i; i = e[i].next) {
         int v = e[i].to;
         if (v == pre) continue;
         S[u]++;
         dfs(v, u);
         w[u] = w[u] * w[v] % MOD, sum[u] += sum[v];
    }
    w[u] = w[u] * jc[S[u]] % MOD;
}
inline void dfs1(int u, int pre) {
    f[u][0][0] = 1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == pre) continue;
        for (int j = S[u]; j >= 1; j--) {
            for (int k = sum[u]; k >= sum[v]; k--) f[u][j][k] = ((f[u][j][k] + f[u][j - 1][k - sum[v]]) >= MOD ? (f[u][j][k] + f[u][j - 1][k - sum[v]]) - MOD : (f[u][j][k] + f[u][j - 1][k - sum[v]]));
        }
        dfs1(v, u);
    }
}
inline void dfs2(int u, int pre) {
    f[u][0][0] = 1;
    if (u == 1) ans[1][1] = 1;
    else if (u != 1) {

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) dp[i][j] = 0;
        }
        dp[1][sum[u]] = (f[pre][1][sum[u]] - 1 + MOD) % MOD;
        for (int i = 1; i <= S[pre]; i++) {
            for (int j = 0; j <= sum[pre]; j++) {
                if (i == 1 && j == sum[u]) continue;
                else if ((i < S[pre] && j < sum[u]) ) dp[i][j] = f[pre][i][j];
                else dp[i][j] = (f[pre][i][j] - dp[i - 1][j - sum[u]] < 0 ? f[pre][i][j] - dp[i - 1][j - sum[u]] + MOD : f[pre][i][j] - dp[i - 1][j - sum[u]]);
            }
        }

        for (int j = 0; j < n; j++) now[j] = 0;
        now[0] = jc[S[pre] - 1] * w[pre] % MOD * qmi(w[u], MOD - 2) % MOD * qmi(jc[S[pre]], MOD - 2) % MOD;
        ll xs = w[pre] % MOD * qmi(w[u], MOD - 2) % MOD * qmi(jc[S[pre]], MOD - 2) % MOD;
        for (int i = 1; i < S[pre]; i++) {
            for (int j = 1; j <= sum[pre]; j++) now[j] = (now[j] + dp[i][j] * jc[i] % MOD * jc[S[pre] - i - 1] % MOD * xs % MOD) % MOD;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) ans[u][j] = (ans[u][j] + ans[pre][i] * now[j - i - 1] % MOD) % MOD;
        }
    }
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == pre) continue;
        for (int j = S[u]; j >= 1; j--) {
            for (int k = sum[u]; k >= sum[v]; k--) f[u][j][k] = ((f[u][j][k] + f[u][j - 1][k - sum[v]]) >= MOD ? (f[u][j][k] + f[u][j - 1][k - sum[v]]) - MOD : (f[u][j][k] + f[u][j - 1][k - sum[v]]));
        }
        //dfs2(v, u);
    }
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == pre) continue;
        dfs2(v, u);
    }
}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
           f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
inline ll R() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
           f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
int main() {
    n = read();
    for (int i = 1; i <= n - 1; i++) {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    jc[0] = 1;
    for (ll i = 1; i <= n; i++) jc[i] = jc[i - 1] * i % MOD;
    dfs(1, 0);
    //dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) printf("%lld ", ans[i][j] * w[i] % MOD);
        printf("\n");
    }
    return 0;
}