2023-10-06

题目

Centroid Probabilities

难度&重要性(1~10):8

题目来源

luogu

题目算法

组合数学，dp

解题思路

首先我们需要处理一下如何去满足好树的条件。很容易想到，当我们定点 \(1\) 为根节点时，每次让结点编号小的当结点编号大的父亲。这样我们就可以保证得到的树是一颗好树，同时能够证明这是不重不漏的。

然后我们考虑如何去判断点 \(i\) 是重心。但这样很难，我们不妨把重心这个条件转换一下，变为点 \(i\) 的子树大小 \(\ge \dfrac{n+1}{2}\) 的方案数。这样转变有什么好处呢，好就是处由于小的结点是大的结点的父亲，我们确定了好树的重心是在点 \(i\) 的子树内的，这样我们只需要容斥一下就可以得到答案了。

我们记 \(f_i\) 表示以 \(i\) 为根结点的子树大小 \(\ge \dfrac{n+1}{2}\) 的方案数。然后我们就可以得到一个比较暴力的转移式：

\[f_i=\begin{cases}(n-1)! & i=1\\ \sum\limits_{j=\frac{n+1}{2}}^{n-i+1}C_{n-i}^{j-1}(n-j-1)!(j-1)!(i-1) & 1<i\le \frac{n+1}{2}\\0 & \frac{n+1}{2}< i\le n\end{cases} \]

主要解释一下当 \(1<i\le \frac{n+1}{2}\) 时的情况，我们设当前子树内包括 \(i\) 共有 \(j\) 个结点，则子树外部就有 \(n-j\) 个结点。对于子树中除了点 \(i\) 的 \(j-1\) 个结点可以在所有大于 \(i\) 的点中选择，方案为 \(C_{n-i}^{j-1}\)。再考虑每一个结点连边的方案：

对于点 \(i\) 可以连向点 \(1\sim i-1\)；
对于子树内的 \(j-1\) 个点，编号第 \(k\) 大的点就有 \(j-k\) 个点可以连，总方案数就是 \((j-1)!\)；
对于子树之外的 \(n-j\) 个点，编号第 \(k\) 大的点就有 \(n-j-k\) 个点可以选择，总方案数为 \((n-j-1)!\)。

这样合起来就是：

\[f_i=\sum\limits_{j=\frac{n+1}{2}}^{n-i+1}C_{n-i}^{j-1}(n-j-1)!(j-1)!(i-1) \]

对于 \(i=1\) 和 \(\dfrac{n+1}{2}<i\le n\) 的情况我们都可以 \(O(1)\) 得到，但是对于 \(1<i\le \frac{n+1}{2}\) 情况的时间复杂度是 \(O(n)\) 的，我们接受不了，需要化简一下。

\[\begin{aligned}f_i= & \sum\limits_{j=\frac{n+1}{2}}^{n-i+1}C_{n-i}^{j-1}(n-j-1)!(j-1)!(i-1)\\= & \sum\limits_{j=\frac{n+1}{2}}^{n-i+1}\dfrac{(n-i)!(n-j-1)!(j-1)!(i-1)}{(j-1)!(n-i-j+1)!}\\= & \sum\limits_{j=\frac{n+1}{2}}^{n-i+1}\dfrac{(n-i)!(n-j-1)!(i-1)}{(n-i-j+1)!}\\= & \sum\limits_{j=\frac{n+1}{2}}^{n-i+1}\dfrac{(n-j-1)!(i-2)!(i-1)}{(n-i-j+1)!(i-2)!}(n-i)!\\= & \sum\limits_{j=\frac{n+1}{2}}^{n-i+1}\dfrac{(n-j-1)!}{(n-j-i+1)!(i+2)!}(n-i)!(i-1)!\\= & (n-i)!(i-1)!\sum\limits_{j=\frac{n+1}{2}}^{n-i+1}C_{n-j-1}^{n-i-j+1}\\= & C_{n-\frac{n+1}{2}}^{n-\frac{n+1}{2}-i+1}(n-i)!(i-1)!\end{aligned} \]

这样我们就可以 \(O(1)\) 解决了 \(f_i\)。

然后考虑得到答案，即将 \(f_i\) 中重心不为 \(i\) 的点容斥掉。在这里的处理我对于其他的题解有少许的疑惑，但仔细的想了想发现是对的。

我们知道在 \(i\) 的子树中的 \(j\) 这个结点是一定对 \(f_i\) 有贡献的，但其实这里的 \(j\) 个结点是从 \(n-i\) 个结点中随机挑选出来的，所以对于重心的祖先结点是均匀分布在 \([1,i]\) 之中的，对于 \(f_i\) 的贡献是 \(\dfrac{1}{i}\) 的。即 \(ans_i=\dfrac{1}{i}f_i\sum\limits_{j=i+1}^nans_j\)。简单的后缀和即可解决。

时间复杂度 \(O(n)\)。