重心概率题解

思路

每个顶点 $v>1$ 都恰好选择一个编号更小的父亲，因此任意父亲序列都对应一棵以 $1$ 为根的递增树，总树数为 $(n-1)!$。令

$$m=\frac{n-1}{2}.$$

对于顶点 $i$，记 $A_i$ 为以 $i$ 为根的子树大小至少为 $m+1$ 的递增树数量， $C_i$ 为顶点 $i$ 是重心的递增树数量。

做法

子任务 1：子树大小分布 DP

固定根 $i$。按编号从 $i+1$ 到 $n$ 加入新顶点，令 $dp_s$ 表示当前 $i$ 的子树 大小为 $s$ 的父亲选择方案数。处理顶点 $v$ 时，它有 $s$ 个父亲会使其加入该子树， 另有 $v-1-s$ 个父亲使其留在子树外，因此

$$dp'_{s+1}\mathrel{+}=s\,dp_s,\qquad dp'_s\mathrel{+}=(v-1-s)dp_s.$$

初始时 $dp_1=(i-1)!$，最后把 $s\ge m+1$ 的状态相加即得 $A_i$。对每个 $i$ 独立执行这套分布 DP，总复杂度为 $O(n^3)$，可以通过 $n\le201$。另外，对 $n\le9$ 还可枚举全部 $(n-1)!$ 个父亲序列，作为完全独立的正确性核验。

子任务 2：枚举子树大小

固定 $i\ge2$，再固定 $i$ 的子树大小为 $k$。从 $i+1,\ldots,n$ 中选出 $k-1$ 个后代后，按递增树的父亲选择规则计数，可得方案数

$$(i-1)\,(n-i)!\,\frac{(n-k-1)!}{(n-i-k+1)!}.$$

因此

$$A_i=(i-1)(n-i)!\sum_{k=m+1}^{n-i+1} \frac{(n-k-1)!}{(n-i-k+1)!},$$

而 $A_1=(n-1)!$。使用阶乘和逆阶乘逐项求和，复杂度为 $O(n^2)$。

一棵奇数点树有唯一重心。若 $i$ 的子树大于一半，则重心必在该子树内；反之，若 重心是 $i$ 的后代，则 $i$ 的子树必大于一半。对于固定的重心 $j>i$，递增树中 “$i$ 是 $j$ 的祖先”的比例为 $1/i$，且重心条件只与 $j$ 的后代结构和子树大小 有关，不受这段祖先选择影响。

令 $S_{i+1}=\sum_{j>i}C_j$，便有

$$A_i=C_i+\frac{S_{i+1}}{i},$$

所以从大到小计算

$$C_i=A_i-\frac{S_{i+1}}i,\qquad S_i=S_{i+1}+C_i.$$

子任务 3：化简组合和式

把子任务 2 的求和变量改写后使用曲棍球棒恒等式：

$$\sum_{r=0}^{m-i+1}\frac{(r+i-2)!}{r!} =(i-2)!\binom{m}{i-1}.$$

于是对 $1\le i\le m+1$ 都有统一公式

$$A_i=(i-1)!(n-i)!\binom{m}{i-1}.$$

当 $i>m+1$ 时，顶点 $i$ 的子树最多有 $n-i+1\le m$ 个点，不可能成为重心， 故 $C_i=0$。预处理阶乘、逆阶乘和逆元后，即可在线性时间算出所有 $A_i,C_i$。

也可以用相邻项递推独立核验公式：

$$A_1=(n-1)!,\qquad A_{i+1}=A_i\frac{m-i+1}{n-i}.$$

正确性证明

父亲序列与合法递增树一一对应。子任务 1 的两个转移分别枚举新顶点的父亲是否在 当前子树中，选择数之和始终为 $v-1$，所以分布 DP 不重不漏。对子任务 2，固定 $i$ 的子树顶点集合及大小后，子树内部与外部的父亲选择相互独立；逐个乘起可选父亲 数便得到所列固定 $k$ 方案数，因此求和恰好得到 $A_i$。

在任意奇数点树中，从根开始不断走向大小超过 $m$ 的唯一儿子，最终停下的位置就是 唯一重心。因此“$i$ 的子树大小超过 $m$”等价于“重心位于 $i$ 的子树内”。当重心 $j>i$ 固定时，$j$ 的祖先结构仍是标准递增树祖先选择；$i$ 成为 $j$ 祖先的概率为 $1/i$。于是 $A_i=C_i+S_{i+1}/i$，逆序递推不重不漏地恢复每个 $C_i$。

最后，组合恒等式把同一个精确的 $A_i$ 求和式化为闭式，并未改变计数对象。故满分 算法输出的每个 $C_i$ 都等于顶点 $i$ 成为重心的合法树数。

复杂度

• 子任务 1：时间 $O(n^3)$，空间 $O(n)$。
• 子任务 2：时间 $O(n^2)$，空间 $O(n)$。
• 子任务 3：时间 $O(n)$，空间 $O(n)$。