P9454 题解

· · 题解

传送门

图满足任何两点之间的简单路径至多只有一条不经过 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)。