题解：P14016 [ICPC 2024 Nanjing R] 拓扑

SUNCHAOYI · 2025-09-11 11:15:01 · 题解

:::info[Hint]

定义：一棵有根树形成的任一排列 p，若 i 是 j 的父亲，排列 p 均满足 i 在 j 之前。更加形式化的，\forall 1 \le i < j \le n，p_j 均不是 p_i 的父亲。
结论：设 f_u 表示以 u 为根时该子树的合法拓扑序的数量，sz_u 表示子树大小，则有 f_u = \dfrac{sz_u!}{\prod sz_v \mid v \in \rm{subtree}(u)}。

以下是证明：

首先考虑二叉树的情况。若以 u 为根，此时每颗子树内的相对顺序是确定的，只需要考虑子树间的相对顺序。故有：

f_u = f_{v_1} \times f_{v_2} \times \binom {sz_{v_1} + sz_{v_2}}{sz_{v_1}}

若是三叉树，考虑将 v_1 与 v_2 的相对顺序先固定形成一个整体后，再考虑 v_3，则可得：

f_u = f_{v_1} \times f_{v_2} \times f_{v_3} \times \binom {sz_{v_1} + sz_{v_2}}{sz_{v_1}} \times \binom {sz_{v_1} + sz_{v_2} + sz_{v_3}}{sz_{v_1} + sz_{v_2}} \newline = f_{v_1} \times f_{v_2} \times f_{v_3} \times \dfrac{\left(sz_{v_1} + sz_{v_2} + sz_{v_3}\right)!}{sz_{v_1}!sz_{v_2}!sz_{v_3}!}

推广到一般，则可推出：

f_u = \left(\prod \limits_{v \in \rm{son}(u)} f_v\right)\times \dfrac{(sz_u - 1)!}{\prod \limits_{v \in \rm{son}(u)} (sz_v!)} \newline = (sz_u - 1)! \prod \limits_{v \in \rm{son}(u)} \left(\dfrac{f_v}{sz_v!}\right)

再由 (sz_u - 1)! = \frac{sz_u!}{sz_u} 做进一步的化简：

继续迭代可得：

f_u = \dfrac{sz_u!}{\prod \limits_{v \in \rm{subtree}(u)}sz_v}

:::

设 dp_{i,j} 表示节点 i 位于第 j 个位置的方案数。若 u 是 v 的父亲，则当 dp_{u,i} 转移至 dp_{v,j} 时，由于 u 内存在其余子树，为了方便转移，方程中 dp_{i,j} 不考虑子树 i 内的顺序，在统计答案的时候再作更新。当 dp_{u,i} 转移至 dp_{v,j} 时，需要考虑的就是 u 的其余子树在整一拓扑序中的位置，以及 u 的其余子树的相对拓扑序。前者就是用组合数求出在剩余的位置中找 sz_u - sz_v - 1 个将 u 内不含 v 子树内的节点放入的方案数，后者直接套结论（见上方 Hint）。故有：

dp_{v,j} = \sum \limits_{i = 1}^{j - 1} dp_{u,i} \times \binom{n - i - sz_v}{sz_u - sz_v - 1} \times \dfrac{(sz_u - sz_v - 1)!}{\prod \limits_{w \in \rm{subtree}(u) \land w \notin \rm{subtree}(v)} sz_w}

最后的答案便是：

dp_{i,i} \times \binom{n - i}{sz_i - 1} \times \dfrac{sz_i!}{\prod \limits_{v \in \rm{subtree}(i) }sz_v}

注意到转移方程可以前缀和优化，所以最后的时间复杂度是 O(n^2)。千万需要先预处理出逆元，O(n^2 \log n) 的做法在 CF 上会挂。放个核心代码吧：

void dfs1 (int u,int fa)
{
    sz[u] = prod[u] = 1;
    for (auto v : ve[u])
    {
        if (v == fa) continue;
        dfs1 (v,u);
        sz[u] += sz[v];
        prod[u] = 1ll * prod[u] * prod[v] % MOD;
    }
    prod[u] = 1ll * prod[u] * sz[u] % MOD;
}
void dfs2 (int u,int fa)
{
    for (auto v : ve[u])
    {
        if (v == fa) continue;
        int tmp = qpow (1ll * prod[u] * inv_prod[v] % MOD * inv_sz[u] % MOD,MOD - 2);
        for (int j = 1;j <= n;++j) ndp[j] = (1ll * dp[u][j] * calc (n - j - sz[v],sz[u] - sz[v] - 1) % MOD + ndp[j - 1]) % MOD;
        for (int j = 1;j <= n;++j) dp[v][j] = 1ll * ndp[j - 1] * f[sz[u] - sz[v] - 1] % MOD * tmp % MOD;
        dfs2 (v,u);
    }
}