题解：P11736 [集训队互测 2015] 胡策的小树
Glacy
·
·
题解
先不管 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)。