解题思路
设树的节点数为 nnn,对任意根 rrr,定义:
* szr(u)\displaystyle sz_r(u)szr (u):以 uuu 为根的子树大小;
* dpr(u)\displaystyle dp_r(u)dpr (u):从 uuu 出发随机 BFS 其子树的方案数。
算法分三步:
1. 预处理
* 预计算阶乘 fact[i]=i! mod M\mathrm{fact}[i] = i! \bmod Mfact[i]=i!modM 和逆元阶乘 invfact[i]=(i!)−1 mod M\mathrm{invfact}[i] = (i!)^{-1} \bmod Minvfact[i]=(i!)−1modM(M=998244353M=998244353M=998244353)。
2. 初始 DFS(根为 0)
自底向上计算 sz0(u)sz_0(u)sz0 (u) 和 dp0(u)dp_0(u)dp0 (u):
sz0(u)=1+∑v∈child(u)sz0(v),sz_0(u) = 1 + \sum_{v \in \mathrm{child}(u)} sz_0(v),sz0 (u)=1+∑v∈child(u) sz0 (v),
dp0(u)=(∑vsz0(v))!⋅∏v∈child(u)dp0(v)sz0(v)! mod M.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.dp0 (u)=(∑v sz0 (v))!⋅∏v∈child(u) sz0 (v)!dp0 (v) modM.
等价形式(化简后):
dp0(u)=∏vdp0(v)⋅(sz0(u)−1)!∏vsz0(v)! mod M.dp_0(u) = \prod_{v} dp_0(v) \cdot \frac{(sz_0(u)-1)!}{\prod_v sz_0(v)!} \bmod M.dp0 (u)=∏v dp0 (v)⋅∏v sz0 (v)!(sz0 (u)−1)! modM.
3. 重根 DP(Rerooting)
沿边 (u,v)(u,v)(u,v) 转移根时,分两步更新:
* 摘除子树 vvv(从 uuu 侧):
szu′=szu−szv,dpu′=dpu⋅(dpv)−1⋅(szu′−1)!(szu−1)!⋅szv! mod M.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.szu′ =szu −szv ,dpu′ =dpu ⋅(dpv )−1⋅(szu −1)!(szu′ −1)! ⋅szv !modM.
* 接入子树 uuu(到 vvv 侧):
szv′=szv+szu′,dpv′=dpv⋅dpu′⋅(szv′−1)!(szv−1)!⋅szu′! mod M.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.szv′ =szv +szu′ ,dpv′ =dpv ⋅dpu′ ⋅(szv −1)!⋅szu′ !(szv′ −1)! modM.
通过一次后序遍历和一次前序遍历,O(n)O(n)O(n) 时间内完成所有根的 dpr(r)dp_r(r)dpr (r) 计算。
输出:对每个节点 iii,输出 dpi(i) mod 998244353dp_i(i) \bmod 998244353dpi (i)mod998244353。
复杂度:时间 O(n)O(n)O(n),空间 O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码解释