定义：一棵有根树形成的任一排列
p p p ，若
i i i 是
j j j 的父亲，排列
p p p 均满足
i i i 在
j j j 之前。更加形式化的，
∀ 1 ≤ i < j ≤ n \forall 1 \le i < j \le n ∀1 ≤ i < j ≤ n ，
p j p_j p j 均不是
p i p_i p i 的父亲。
结论：设
f u f_u f u 表示以
u u u 为根时该子树的合法拓扑序的数量，
s z u sz_u s z u 表示子树大小，则有
f u = s z u ! ∏ s z v ∣ v ∈ s u b t r e e ( u ) f_u = \dfrac{sz_u!}{\prod sz_v \mid v \in \rm{subtree}(u)} f u = ∏ s z v ∣ v ∈ subtree ( u ) s z u ! 。
以下是证明：
首先考虑二叉树的情况。若以
u u u 为根，此时每颗子树内的相对顺序是确定的，只需要考虑子树间的相对顺序。故有：
f u = f v 1 × f v 2 × ( s z v 1 + s z v 2 s z v 1 ) f_u = f_{v_1} \times f_{v_2} \times \binom {sz_{v_1} + sz_{v_2}}{sz_{v_1}} f u = f v 1 × f v 2 × ( s z v 1 s z v 1 + s z v 2 ) 若是三叉树，考虑将
v 1 v_1 v 1 与
v 2 v_2 v 2 的相对顺序先固定形成一个整体后，再考虑
v 3 v_3 v 3 ，则可得：
f u = f v 1 × f v 2 × f v 3 × ( s z v 1 + s z v 2 s z v 1 ) × ( s z v 1 + s z v 2 + s z v 3 s z v 1 + s z v 2 ) = f v 1 × f v 2 × f v 3 × ( s z v 1 + s z v 2 + s z v 3 ) ! s z v 1 ! s z v 2 ! s z 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 = f v 1 × f v 2 × f v 3 × ( s z v 1 s z v 1 + s z v 2 ) × ( s z v 1 + s z v 2 s z v 1 + s z v 2 + s z v 3 ) = f v 1 × f v 2 × f v 3 × s z v 1 ! s z v 2 ! s z v 3 ! ( s z v 1 + s z v 2 + s z v 3 ) ! 推广到一般，则可推出：
f u = ( ∏ v ∈ s o n ( u ) f v ) × ( s z u − 1 ) ! ∏ v ∈ s o n ( u ) ( s z v ! ) = ( s z u − 1 ) ! ∏ v ∈ s o n ( u ) ( f v s z v ! ) 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) f u = ( v ∈ son ( u ) ∏ f v ) × v ∈ son ( u ) ∏ ( s z v !) ( s z u − 1 )! = ( s z u − 1 )! v ∈ son ( u ) ∏ ( s z v ! f v ) 再由
( s z u − 1 ) ! = s z u ! s z u (sz_u - 1)! = \frac{sz_u!}{sz_u} ( s z u − 1 )! = s z u s z u ! 做进一步的化简：
继续迭代可得：
f u = s z u ! ∏ v ∈ s u b t r e e ( u ) s z v f_u = \dfrac{sz_u!}{\prod \limits_{v \in \rm{subtree}(u)}sz_v} f u = v ∈ subtree ( u ) ∏ s z v s z u ! 设
d p i , j dp_{i,j} d p i , j 表示节点
i i i 位于第
j j j 个位置的方案数。若
u u u 是
v v v 的父亲，则当
d p u , i dp_{u,i} d p u , i 转移至
d p v , j dp_{v,j} d p v , j 时，由于
u u u 内存在其余子树，为了方便转移，方程中
d p i , j dp_{i,j} d p i , j 不考虑子树
i i i 内的顺序，在统计答案的时候再作更新。当
d p u , i dp_{u,i} d p u , i 转移至
d p v , j dp_{v,j} d p v , j 时，需要考虑的就是
u u u 的其余子树在整一拓扑序中的位置，以及
u u u 的其余子树的相对拓扑序。
前者就是用组合数求出在剩余的位置中找
s z u − s z v − 1 sz_u - sz_v - 1 s z u − s z v − 1 个将
u u u 内不含
v v v 子树内的节点放入的方案数，后者直接套结论（见上方 Hint）。故有：
d p v , j = ∑ i = 1 j − 1 d p u , i × ( n − i − s z v s z u − s z v − 1 ) × ( s z u − s z v − 1 ) ! ∏ w ∈ s u b t r e e ( u ) ∧ w ∉ s u b t r e e ( v ) s z w 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} d p v , j = i = 1 ∑ j − 1 d p u , i × ( s z u − s z v − 1 n − i − s z v ) × w ∈ subtree ( u ) ∧ w ∈ / subtree ( v ) ∏ s z w ( s z u − s z v − 1 )! 最后的答案便是：
d p i , i × ( n − i s z i − 1 ) × s z i ! ∏ v ∈ s u b t r e e ( i ) s z v dp_{i,i} \times \binom{n - i}{sz_i - 1} \times \dfrac{sz_i!}{\prod \limits_{v \in \rm{subtree}(i) }sz_v} d p i , i × ( s z i − 1 n − i ) × v ∈ subtree ( i ) ∏ s z v s z i ! 注意到转移方程可以前缀和优化，所以最后的时间复杂度是
O ( n 2 ) O(n^2) O ( n 2 ) 。千万需要先预处理出逆元，
O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) 的做法在 CF 上会挂。放个核心代码吧：
CPP void dfs1 (int u,int fa)
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);
}
}