ACGO巅峰赛#22+题解

解题思路

设树的节点数为 $n$，对任意根 $r$，定义：

• $\displaystyle sz_r(u)$：以 $u$ 为根的子树大小；
• $\displaystyle dp_r(u)$：从 $u$ 出发随机 BFS 其子树的方案数。

算法分三步：

1. 预处理

   • 预计算阶乘 $\mathrm{fact}[i] = i! \bmod M$ 和逆元阶乘 $\mathrm{invfact}[i] = (i!)^{-1} \bmod M$（$M=998244353$）。

2. 初始 DFS（根为 0）
   自底向上计算 $sz_0(u)$ 和 $dp_0(u)$：
   $sz_0(u) = 1 + \sum_{v \in \mathrm{child}(u)} sz_0(v),$
   $dp_0(u) = \left( \sum_{v} sz_0(v) \right)! \cdot \prod_{v \in \mathrm{child}(u)} \frac{dp_0(v)}{sz_0(v)!} \bmod M.$
   等价形式（化简后）：
   $dp_0(u) = \prod_{v} dp_0(v) \cdot \frac{(sz_0(u)-1)!}{\prod_v sz_0(v)!} \bmod M.$

3. 重根 DP（Rerooting）
   沿边 $(u,v)$ 转移根时，分两步更新：

   • 摘除子树 $v$（从 $u$ 侧）：
     $sz_u' = sz_u - sz_v, \quad dp_u' = dp_u \cdot (dp_v)^{-1} \cdot \frac{(sz_u'-1)!}{(sz_u-1)!} \cdot sz_v! \bmod M.$
   • 接入子树 $u$（到 $v$ 侧）：
     $sz_v' = sz_v + sz_u', \quad dp_v' = dp_v \cdot dp_u' \cdot \frac{(sz_v'-1)!}{(sz_v-1)! \cdot sz_u'!} \bmod M.$
     通过一次后序遍历和一次前序遍历，$O(n)$ 时间内完成所有根的 $dp_r(r)$ 计算。

输出：对每个节点 $i$，输出 $dp_i(i) \bmod 998244353$。
复杂度：时间 $O(n)$，空间 $O(n)$。

---

代码解释

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
const int MOD = 998244353;

int n;
vector<int> adj[MAXN];
long long fact[MAXN], invfact[MAXN];

long long qpow(long long a, long long b) {
    long long res=1;
    while(b) {
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}

long long comb(int a,int b) {
    if(b > a || b < 0) return 0;
    return fact[a]*invfact[b]%MOD*invfact[a-b]%MOD;
}

long long multinomial(int total, const vector<int>& parts) {
    long long res = fact[total];
    for(auto x: parts) res = res * invfact[x] % MOD;
    return res;
}

int sz[MAXN];
long long f[MAXN];

void dfs1(int u, int fa) {
    sz[u] = 1;
    vector<int> parts;
    long long res=1;
    for(auto v : adj[u]) {
        if(v == fa) continue;
        dfs1(v,u);
        sz[u] += sz[v];
        parts.push_back(sz[v]);
        res = res * f[v] % MOD;
    }
    if(!parts.empty()) res = res * multinomial(sz[u]-1, parts) % MOD;
    f[u] = res;
}

long long ans[MAXN];

void reroot(int u, int fa) {
    ans[u] = f[u];
    for(auto v : adj[u]) {
        if(v == fa) continue;
        int su = sz[u], sv = sz[v];
        long long fu = f[u], fv = f[v];
        f[u] = f[u] * qpow(f[v], MOD-2) % MOD;
        f[u] = f[u] * fact[su - sv - 1] % MOD;
        f[u] = f[u] * invfact[su - 1] % MOD;
        f[u] = f[u] * fact[sv] % MOD;
        sz[u] = su - sv;
        f[v] = f[v] * f[u] % MOD;
        f[v] = f[v] * fact[sv + sz[u] - 1] % MOD;
        f[v] = f[v] * invfact[sv - 1] % MOD;
        f[v] = f[v] * invfact[sz[u]] % MOD;
        sz[v] = sv + sz[u];
        reroot(v, u);
        f[u] = fu; f[v] = fv;
        sz[u] = su; sz[v] = sv;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i=1;i<n;i++){
        int u,v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    fact[0] = invfact[0] = 1;
    for(int i=1;i<=n;i++) fact[i] = fact[i-1]*i%MOD;
    invfact[n] = qpow(fact[n], MOD-2);
    for(int i=n-1;i>=1;i--) invfact[i] = invfact[i+1]*(i+1)%MOD;
    dfs1(0,-1);
    reroot(0,-1);
    for(int i=0;i<n;i++) cout << ans[i] << "\n";
    return 0;
}