2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus)

G

给出\(n,n\le 1000000\)，求\(n\)个点编号分别为\(1\)到\(n\)的树有多少种存在二分图完美匹配。

注意到判断一棵具体的树是否存在二分图完美匹配比较难搞并且计数的复杂度无法接受，考虑先把1~n的排列分成n/2个二元组表示某个完美匹配，再在匹配边之间连接\(\frac{n}{2}-1\)条边使其变成一棵树

把排列分成\(n/2\)个内部有序的二元组的方案数是\(n\)的全排列的方案数除以相邻位置俩俩配对形成的\(n/2\)个元素的全排列方案数，即\(\frac{n!}{\frac{n}{2}!}\). 那它们之间连边形成一棵树的方案数呢？

统计树的方案数，可以借助\(prufer\)​序列。

\(prufer\)序列的构造方法是：每次找到编号最小的叶子节点（度数为1的点），删除该节点并把与其相连的点的编号加入当前序列的末端，重复上述操作直到整棵树中只剩下2个点。

通过\(prufer\)​​序列得到无根树，可以考虑逆向执行上述过程：每次找出prufer序列首的点u，将点集（初始为{1,2,...,n}）中最小的没有在prufer序列中出现的结点记为v，在u，v之间连边并从点集中删除v，从prufer序列中删除u（注意prufer序列的后面可能还有u，此处删除的是当前序列首的u）。按照这样操作，当prufer序列为空时，点集中只剩下两个点，在其之间连边，树的构建就完成了。