ARC155F Directable as Desired

引理：对于给定的 \(k\) 个点，生成 \(k\) 个内向森林且根为给定的 \(k\) 个点的方案数为 \(kn^{n-k-1}\)。

证明：考虑执行 \(n-k\) 轮操作，每次选择任意一个点向不再其若连通块的点连一条有向边，那么方案数为 \(\prod_{i=1}^{n-k}n(n-i)=n^{n-k}\frac{(n-1)!}{(k-1)!}\)，但这 \(n-k\) 条边的加入此时是有顺序的，将其无序化的方案数为 \(n^{n-k}\frac{(n-1)!}{(k-1)!(n-k)!}\)，而此时选中的点可能产生任意一个 \(\binom{n}{k}\) 的方案，则最后除掉方案数则为 \(n^{n-k}\frac{(n-1)!}{(k-1)!(n-k)!\binom{n}{k}}=kn^{n-k-1}\)。

那么对于原问题，我们限定 \(1\) 为根，将所有与父亲连边朝向根的加入集合 \(S\)，令 \(|S|=k\)，一开始我们将 \(S\) 中的点与父亲相连，那么相当于生成 \(n-k\) 个内向森林且根为剩下的 \(n-k\) 个点的方案数，为 \((n-k)n^{k-1}\)，之后将所有度数的点向下连边，此时在 \(S\) 中的点还可以连 \(d_{i}-1\) 条边，不再 \(S\) 中的点还可以连 \(d_{i}\) 条边，共连 \((n-k-1)\) 条边，如果枚举每条出边连向不在其弱连通块的根，则有 \((n-k-1)!\) 种方案，但每个点的出边是无序的，所以还要除 \(\prod_{i=1}^{n}(d_{i}-(i\in S))!\)，但此时根不一定为 \(1\)，注意到这样求出来的所有根的答案和，且最终所有根的方案数是一样的，最后除以 \(n\) 即可。

枚举 \(S\) 的过程可以视为卷积形式，可以分治 \(FFT\) 做到 \(O(n log^2 n)\)。