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序列為空時，點集中隻剩下兩個點，在其之間連邊，樹的建構就完成了。