自动搬运

查看原文

来自洛谷，原作者为

	Glacy Glacy is Sylvy, not Spacy

搬运于2025-08-24 23:09:51，当前版本为作者最后更新于2025-02-15 16:27:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

先不管 $x$ 我们来算一下答案。

设猴子在充分长时间后，随机一个时刻（显然时刻之间是等价的）点 $i$ 的概率为 $f_i$，此时期望值应为 $\sum f_ip_i$。至于初始局面不满足该分布的问题，由于题目中的操作数相对于精度过于巨大，可以忽略掉最开始这一部分局面的贡献。

如何求解 $f_i$ 是容易的。具体地，考察一次移动，显然这两次之间 $f$ 是相同的，所以可以直接写出方程（这么做的正确性并不显然，读者可自行思考此部分）：

$$\sum_{v\in \text{subtree}(u)}f_v =\sum_{v\in\text{subtree}(u),v\neq u} f_v+\sum_{u\in \text{subtree}(v)} f_v(1-p_v)sz_u/sz_v $$

两边减去 $\sum_{v\in\text{subtree}(u),v\neq u}f_v$，得到：

$$f_u=\sum_{u\in \text{subtree}(v)} f_v(1-p_v)sz_u/sz_v $$

将右侧关于 $f_u$ 的项提出来：

$$f_u=\frac{\sum_{u\in \text{subtree}(v),u\neq v} f_v(1-p_v)sz_u/sz_v}{p_u} $$

因此，有：

$$\frac{p_u}{sz_u}f_u = \sum_{u\in \text{subtree}(v),u\neq v}\frac{f_v(1-p_v)}{sz_v}=\frac{p_{fa_u}}{sz_{fa_u}}f_{fa_u}+\frac{f_{fa_u}(1-p_{fa_u})}{siz_{fa_u}}=\frac{f_{fa_u}}{sz_{fa_u}} $$

于是可以使用树上高斯消元 $O(n)$ 计算。

现在考虑有 $x$ 的情况，枚举所有 $x$，因为题目中的式子是一个置换，所以恰好会有一个 $u$ 满足 $p_u=0$。显然只有该点的子树内 $f$ 非 $0$，所以只需要对这棵子树计算答案。总复杂度为所有子树的大小之和，由数据随机方式可知为期望 $O(n\log n)$。