题解 CF1667E

考虑枚举每个点 $i$，记 $f_i$ 为子树 $i$ 大小 $\geq \frac{n+1}{2}$ 的方案数。 先考虑子树 $i$ 的大小为 $j$ 的方案数，首先要在 $i+1$ 到 $n$ 号点中选 $j-1$ 个放入子树 $i$，这部分方案数为 $\binom{n-i}{j-1}$ 。然后给子树 $i$ 中的点钦定父子关系，方案数为 $(j-1)!$ 。对子树 $i$ 以外的点钦定父子关系，方案数为 $(n-j-1)!$ 。还要考虑 $i$ 的父亲，方案数为 $(i-1)$。 综上，子树 $i$ 的大小为 $j$ 的方案数为： $$\binom{n-i}{j-1} (j-1)! (n-j-1)! (i-1)$$ 注意，这个式子在 $i=1$ 时显然不成立，简单特判即可。 发现上面的式子还可以拆阶乘变成： $$(n-i)!(i-1)!\binom{n-1-j}{i-2}$$ 我们枚举 $j$ 的范围为 $[\frac{n+1}{2},n]$，令 $k=n-1-j$，则 $k$ 的范围为 $[0,\frac{n-3}{2}]$。由经典的组合恒等式可知，$\sum\limits_{k=0}^{\frac{n-3}{2}}\binom{k}{i-2}=\binom{\frac{n-1}{2}}{i-1}$。 这样，我们就可以在线性复杂度内得到所有的 $f_i$。 但 $f_i$ 不等于 $i$ 为重心的方案数，我们还要容斥掉重心在 $i$ 子树内的情况。 重心在 $i$ 子树内等价于 $i$ 有某个子节点 $v$，满足 $v$ 的子树大小 $\geq \frac{n+1}{2}$，且显然这样的 $v$ 最多只有一个。 考虑对于每个 $i$，枚举所有 $v>i$，计算有多少种方案使 $v$ 子树大小 $\geq \frac{n+1}{2}$ 且 $v$ 为 $i$ 的子节点。 容易发现，当 $v$ 的子树大小固定时，$v$ 的父节点为任意可能点的方案数都是一样的。那么刚刚我们要容斥掉的东西可以直接按 $\frac{f_v}{v-1}$ 来算。 这样，$ans_i=f_i-\sum\limits_{v>i}\frac{f_v}{v-1}$，求完 $f$ 后做一遍后缀和就行了。 时间复杂度：$O(n)$。 完全不能理解这题是怎么放到 1E 的位置上的，没开真是亏大了（