Probabilities
Centroid Probabilities
2023-10-06 题目 Centroid Probabilities 难度&重要性(1~10):8 题目来源 luogu 题目算法 组合数学，dp 解题思路 首先我们需要处理一下如何去满足好树的条件。很容易想到，当我们定点 \(1\) 为根节点时，每次让结点编号小的当结点编号大的父亲。这样我们就 ......
【树论，计数】Centroid Probabilities
生生动动贺题贺一遍！ 考虑先求出 $f_x$ 表示 $x$ 子树大小 $\leq \frac{n + 1}{2}$ 的方案数。 最后再容斥掉 $x + 1 \to n$ 的方案即可。 $$\huge f_x = \sum^{n - x + 1}_{j = \frac{n + 1}{2}} \bino ......