自动搬运

查看原文

来自洛谷，原作者为

	寻逍遥2006 晓看天色暮看云，行也思君，坐也思君；春赏百花冬赏雪，醒也思卿，梦也思卿

搬运于2025-08-24 22:48:31，当前版本为作者最后更新于2023-07-09 07:27:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

图满足任何两点之间的简单路径至多只有一条不经过 $1$ 节点，所以删去 $1$ 节点之后，图中如任何两点之间至多只有一条简单路径。则删去 $1$ 节点之后的图构成森林，此时的每一个连通块为一颗树（注意不是原图的树）。

所以本题的边数范围是 $n-1\leq m\leq n-2+n-1=2n-3$。

题意为求从 $1$ 开始 dfs，每一个点的 dfs 序期望，也就是要求对于每个节点 $u$ 期望有多少个点在 $u$ 之前深搜到，答案就是其 $+1$。

由于原图满足删去 $1$ 节点之后的图构成森林，所以在进入了某棵树之后，只有将这颗树深搜完才能进入别的树。

考虑将点对间贡献分为树内和树外两种。

先考虑树内贡献：

假如只有一个节点能够作为这整棵树中第一个搜到的节点，我们令其为根。

那么对于树中的一个节点 $u$：$u$ 的祖先必然对 $u$ 做 $1$ 的贡献；$u$ 的子孙必然不对 $u$ 做贡献；其他节点对 $u$ 做 $\frac{1}{2}$ 的贡献，就是在这个点 $v$ 和 $u$ 的 LCA 处先走向 $u$ 或先走向 $v$，二者概率均为 $\frac{1}{2}$。

记 $T_u$ 为 $u$ 所在的树，$anc_u$ 为 $u$ 的祖先集合，$sub_u$ 为 $u$ 的子孙集合，则 $u$ 点在树内的dfs序期望为 $\dfrac{|T_u|+|anc_u|-|sub_u|}{2}$。

对于所有 $|anc_u|$ 和 $|sub_u|$ 的求值是 $O(n)$ 的。

由于有多个节点可能和 $1$ 相连，它们等概率地可能成为这棵树的根，如果暴力对于每一个点进行一次深搜，最坏复杂度是 $O(n^2)$。

改为换根DP，维护每个点到所有可能成为根的点的距离和，以及对于每种根对应的子树大小和。

随便钦定一个点为根，考虑先深搜维护出每个点到子树内所有可能为根的点的距离，以及对于子树内所有点对应的子树大小和。

这两部分均可以实现 $O(1)$ 转移，所以换根DP复杂度为 $O(n)$。

再考虑树间贡献：

对于两颗树 $S$ 和 $T$，我们记它们分别和 $1$ 节点分别有 $cnt_S$ 和 $cnt_T$ 个点相连。

我们考虑 $T$ 节点在 $S$ 节点之前搜到的概率应为 $\dfrac{cnt_T}{cnt_S+cnt_T}$，可以理解为将所有和 $1$ 节点相连的点随意排列作为 $1$ 节点开始深搜的顺序，则 $T$ 树在 $S$ 树之前搜的概率等价于 $T$ 树的 $cnt_T$ 个节点中最靠前的节点在 $S$ 树的 $cnt_S$ 个节点中最靠前的节点之前的概率，等价于在 $cnt_T$ 个黑球和 $cnt_S$ 个白球选出一个球，它是黑色的概率。

所以 $T$ 树对 $S$ 树每个节点的贡献为 $\dfrac{cnt_T|T|}{cnt_S+cnt_T}$。

暴力考虑树间两两贡献的最劣复杂度也是是 $O(n^2)$ 的，尝试优化。

假设对于两棵树 $T_1$ 和 $T_2$，满足 $cnt_{T_1}=cnt_{T_2}$，则它们对于其他树的贡献只有 $|T_1|$ 和 $|T_2|$ 的区别，而和 $S$ 有关的分母是不变的。

所以考虑将所有 $cnt_T=k$ 的数分在一组，然后统一处理，然后剔除掉自己对自己的贡献即可。

由于 $\sum cnt_T\leq n$，所以不同的 $cnt_T$ 只至多 $O(\sqrt{n})$，然后再两两暴力维护复杂度就是 $O(n)$ 的了。

所以总体复杂度是 $O(n)$。