生生动动贺题贺一遍！
考虑先求出 \(f_x\) 表示 \(x\) 子树大小 \(\leq \frac{n + 1}{2}\) 的方案数。
最后再容斥掉 \(x + 1 \to n\) 的方案即可。
即考虑选出子树，生成子树内和子树外的 \(fa_x\)，然后选出一个父亲。推柿子！
\[\sum^{n - x + 1}_{j = \frac{n + 1}{2}} \frac{(n - i)!(n - j - 1)!(i - 1)}{(n - i - j + 1)!} \]\[(i - 1)(n - i)!\sum^{n - x + 1}_{j = \frac{n + 1}{2}} \frac{(n - j - 1)!}{(n - i - j + 1)!} \]\[(i - 1)!(n - i)!\sum^{n - x + 1}_{j = \frac{n + 1}{2}} \binom{n - j - 1}{i - 2} \]然后用魔法：
\[\sum_{k = 0}^{\frac{n - 3}{2}}\binom{k}{i - 2} = \binom{\frac{n - 1}{2}}{i - 1} \]代换 \(m \to \frac{n + 1}{2}\) 可以得到：
\[(i - 1)!(n - i)!\binom{n - m}{i - 1} \]然后直接拆！
\[\frac{(n - m)!(n - i)!}{(n - i - m + 1)!} \]事实上，还没做完。
\[g_x = f_x - \frac{\sum_{k = i + 1} g_k}{x} \] 标签：子树,frac,Probabilities,sum,树论,Centroid,binom From： https://www.cnblogs.com/Custlo/p/17621565.html