[EA练习赛2] 计树
最终的树一定是若干条极长链拼接而成的，一条链的 (OGF) 即为 (sumlimits_{ige 2}x^i=frac{x^2}{1-x}) 。
引理：对于一个划分 (len_1,len_2,...,len_m) ，它的拼接方案数为
[n^{m-2}prodlimits_{i=1}^{m}len_i ]证明：将一条极长链看作一个点，枚举它的度数，每个度数有 (len_i) 种连法，则根据 ( ext{prufer}) 序列有：
[sumlimits_{sumlimits_{i}(deg_i-1)=m-2}frac{(m-2)!}{prodlimits_{i}(deg_i-1)!}prodlimits_{i}len_i^{deg_i} ][=left(prod_{i}len_i ight)left((m-2)![x^{m-2}]prod_{i}e^{len_ix} ight) ][=n^{m-2}prod_{i=1}^{m}len_i ]
由于一条极长链可能被算重（它的几个子链拼接出来），考虑容斥掉几个拼起来的情况。记 (A(x)) 表示容斥系数的生成函数，(x^i) 项的系数表示长度为 (i) 的链对应的容斥系数，有：
[A(x)+A^2(x)+A^3(x)+...=frac{1}{1-A(x)}-1
]
我们希望长度小于 (2) 的区间被统计的次数为 (0) ，长度 (ge 2) 的区间被统计的次数为 (1) :
[frac{1}{1-A(x)}-1=frac{x^2}{1-x}
]
[A(x)=frac{x^2}{x^2-x+1}
]
"虚假"的极长链的贡献为 (f_{len}=left( [x^{len}]frac{x^2}{x^2-x+1} ight) imes len imes n) 。
枚举极长链的个数，最终的答案为
[n^{-2}sumlimits_{i=0}^{n}[x^n]F^i(x)
]
[=n^{-2}[x^n]frac{1}{1-F}
]
多项式求逆即可，时间复杂度 (O(nlogn)) 。