题解 P8334【[ZJOI2022] 深搜】

· · 题解

P8334 [ZJOI2022] 深搜 解题报告：

更好的阅读体验

题意

定义 f(x,y) 合法当且仅当 y 在 x 子树中，其值为对 x 的子树进行 dfs，往下走随机选一个没有访问过的点，遇到 y 时经过的点点权最小值的期望。

求 \sum_{x,y}f(x,y)。

## 分析 可能有点口胡，假了赶紧来喷我（ 离散化，枚举一个 $i$，令权值大于等于 $i$ 的点为黑点，那么我们就是要支持将一个点由黑染白，以及维护简单路径只经过黑点的点对，dfs 时不遇到白点的概率之和。 考虑将子树内有白点的点叫灰点，那么可以发现我们不能 dfs 入没有 $y$ 的灰点子树。转移方程大概长这样：（令 $s(x)$ 为 $x$ 的灰儿子数量） $$f_x=\begin{cases}0&[x\ \text{is}\ \text{white}]\\\sum_{y\in son(x)}\begin{cases}\frac{f_y}{s_x}&[y\ \text{is}\ \text{grey}]\\\frac{size_y}{s_x+1}&\text{otherwise}\end{cases}\end{cases}$$ 这样我们就得到了一个 $O(n^2)$ 的解法。 直接将转移方程刻画成矩阵，每次加入白点的时候暴力更新非灰的祖先（更新单点的转移系数以及一条链的 $f$），用一个全局平衡二叉树就是 $O(n\log n)$ 了。 ## 代码 暂时鸽一手。