【树论，计数】Centroid Probabilities
生生动动贺题贺一遍！
考虑先求出 \(f_x\) 表示 \(x\) 子树大小 \(\leq \frac{n + 1}{2}\) 的方案数。
最后再容斥掉 \(x + 1 \to n\) 的方案即可。
\[\sum^{n - x + 1}_{j = \frac{n + 1}{2}} \binom{n - i}{j - 1}(j - 1)!(n - j - 1)!(i - 1)
\]
即考虑选出子树，生成子树内和子树外的 \(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}
\]
欢迎来到一个广东菜鸡OIFER的博客