题解 P8334【[ZJOI2022] 深搜】

xtx1092515503 · 2022-05-11 16:23:19 · 题解

考虑关于每个权值分开处理：对于权值 V，我们计算 \min\geq V 的概率，则对每个 V 的概率求和即得到最终期望。

对于某个 V，我们记 \geq V 的位置为 黑点，<V 的位置为 白点。

考虑针对路径 x\to y 计算答案。

模拟 dfs 的流程，就能发现，一旦我们进入到某棵 存在白点的子树，则这次搜索就不合法了。

考虑当前在节点 u。记除去 y 所在的子树外，u 还有 c_u 棵存在白点的子树，d_u 棵全黑子树。

在前往 y 所在的子树前不经过任何存在白点的子树的概率是多少呢？

考虑随机一组排列，按照这种顺序访问每棵子树。则，y 所在子树在每个位置被访问的概率均相同，即为 \dfrac1{c_u+d_u+1}。

其在第 i 个位置被访问前不经过任何白子树的概率是 \dfrac{d_u^{\underline{i-1}}}{(c_u+d_u)^{\underline{i-1}}}，则我们要计算 \dfrac1{c_u+d_u+1}\sum\limits_{i=1}^{c_u+d_u+1}\dfrac{d_u^{\underline{i-1}}}{(c_u+d_u)^{\underline{i-1}}}。

稍微推一下式子吧！

而这个式子是很符合直觉的，因为事实上我们摇到纯黑子树可以相当于做了无效决策，故只需找到 y 所在子树在所有非纯黑子树前摇到的概率即可，而该概率即为上式。

令 f_u 表示上式与 [u\text{是黑点}] 的积，则 w(x\to y)=[y\text{是黑点}]\prod\limits_{z\in[x\to y)}f_z，其中 z 枚举到 x，不枚举到 y。

但是我们发现，对于同一个 u 和不同的 y，c_u 可能是不同的（因为 c_u 并不包含 y 所在子树），故 f_u 也是不同的。

但是再注意到对于纯黑子树和非纯黑子树，它们对应的 c_u 各自是相同的。故我们只需对 y 所在子树是 u 的纯黑子树还是非纯黑子树分别讨论一下即可。

到现在，我们已经会一个若干方的垃圾做法了，考虑进一步做点操作。

令 dp_i 表示，x=i 且 y 为 i 子树中全体点时，\sum w(x\to y)。则权值为 c 时的答案即为 \sum dp_i。

考虑用 w 的式子来推出 DP。然后我们发现 dp_x=[x\text{是黑点}]+\sum\limits_{y\in\text{son}_x}dp_yf_{x,y}，其中 f_{x,y} 为 y 所在子树与 x 间的 f 值。

这个式子允许我们在线性时间内对一个权值 V 求解。

现在我们要对多个 V 求解。考虑 V 不同时上述条件的变化。