树上拓扑序个数小记
给定一棵有根外向树，要求对拓扑序个数计数。
设 \(f(x)\) 表示子树 \(x\) 的拓扑序个数，容易写出以下转移（先确定每个子树的拓扑序，再将它们分配）：
\[f(x)= (sz_x-1)!\prod_{v\in son(x)} \dfrac{ f(v)}{ sz_v!}
\]
考虑展开 \(f(v)\) 得到：
\[\begin{aligned}
f(x)&=(sz_x-1)!\prod _{v\in son(x)} \dfrac 1{sz_v!} (sz_v-1)!\prod _{w\in son(v)}\dfrac {f(w)}{sz_w!}\\
&=(sz_x-1)!\prod_{v\in son(x)}\dfrac 1{sz_v}\prod _{w\in son(v)} \dfrac {f(w)}{sz_w!}
\end {aligned}
\]
不断展开最终叶子的 \(f=1\)，因此拓扑序个数是
\[\dfrac {n!} {\prod_{i\in \text{tree}} sz_i}
\]