JSOI2019神经网络 树形DP生成函数

[JSOI2019]神经网络 一条合法的哈密顿路，由两部分组成：每棵树拆成一些独立的链，把链串起来。 考虑如何把树拆成链。令$f_{x,i,0/1/2}$，表示$x$子树内划分为$i$条，并且有$0/1/2$个链连上来。对于子树$y$，是从$y$连上来，对于当前考虑的$x$，是连到$x$的。那么就可以转移了，注意一条链可以有两个端点。 考虑使用EGF求解。第一个树比较特殊，先不管。注意到拼起来之后，不可以有原树上的相邻。那么考虑一个容斥： $$F(x)=\sum_{i=1} \frac{x^i}{i!} \sum_{j=i} \binom{j-1}{i-1}(-1)^{j-i}f_jj!$$ 后面的部分是考虑一下随意拼接，并二项式反演得到的。 对于第一个树，因为已经钦定了起点，就不可以随意排列了。那么有： $$F(x)=\sum_{i=1} \frac{x^{i-1}}{(i-1)!} \sum_{j=i} \binom{j-1}{i-1}(-1)^{j-i}f_jj!$$ 卷起来就是哈密顿路的方案了。这道题要求的是哈密顿环，所以第一个树的还要减去： $$F(x)=\sum_{i=1} \frac{x^{i-2}}{(i-2)!} \sum_{j=i} \binom{j-1}{i-1}(-1)^{j-i}f_jj!$$