P5333 [JSOI2019]神经网络
Solution
EGF 表示有标号排列。
对每棵树分别算出划分成 \(i\) 条链的方案数，记为 \(f_i\)。
具体地：设 \(dp[u][i][0/1/2]\) 表示在 \(u\) 子树内拆分成 \(i\) 条已结束的链，
\(0\): 已拼完，无法再延伸
\(1\): 单点，可继续向上扩展
\(2\): 长度 \(>1\) 的链，且可继续向上扩展 (为了处理正反向方案数 \(\times 2\) 的问题)
对于根节点视作它可以向父节点扩展，即和其它节点同等处理
状态由划分的客观形态决定 不能对 \(1/2\) 情况人为钦定为 \(0\)
\(f_i = dp[root][i][0] + dp[root][i - 1][1] + 2 \times dp[root][i - 1][2]\)
\(dp\) 转移有点繁复，但写出来极度舒适
把所有链拼成一个路径排列，则相邻的链颜色不同。
对于其他树，EGF 为：（采用容斥思想，枚举相邻位置个数）
\[\sum\limits_{i = 1}^{k}f_i\times i! \times \sum\limits_{j = 0}^{i - 1}(-1)^{j}\binom{i - 1}{j}\frac{x^{i - j}}{(i - j)!}
\]
对于第一棵树，第一条链被固定为起点，且第一棵树最后一条链不能与第一条链相邻。
第一条链被固定为起点：但统计一号点不必作为排列的起点，只需平移即可得到合法哈密顿回路。
第一棵树最后一条链不能与第一条链相邻：可以把两条链拼起来看成第一棵树的另一种拆分方案，因此存在计重问题。
在前一个限制下，用任意合法方案减去强行钦定首尾同色的合法方案，得到第一棵树的 EGF：
\[\sum\limits_{i = 1}^{k}f_i\times (i - 1)! \times \sum\limits_{j = 0}^{i - 1}(-1)^{j}\binom{i - 1}{j}\frac{x^{i - j - 1}}{(i - j - 1)!} - \sum\limits_{i = 1}^{k}f_i\times (i - 1)! \times \sum\limits_{j = 0}^{i - 1}(-1)^{j}\binom{i - 1}{j}\frac{x^{i - j - 2}}{(i - j - 2)!}
\]
注意后者最后一条链的选取有 \(i - 1\) 种方案，因此其前面的系数仍为 \((i - 1)!\) 而非 \((i - 2)!\)。
暴力卷积，最后把每一项的系数乘对应的阶乘（化成 EGF 的形式）。