树上随机游走

· · 算法·理论

题目：CF802L

设 f_u 表示从 u 号点出发走到结束时的期望距离

\large f_u=\begin{cases}0&\text{u is a leaf}\\\frac{\sum\limits_{(u,v)\in E}f_v+w_{u,v}}{deg_u}&\text{other cases}\end{cases}

我们要做的是，找到 A_u,B_u，使得 f_u=A_u\cdot f_p+B_u

那么对于 \text{other cases}：

f_u =\frac{\sum\limits_{(u,v)\in E}(f_v+w_{u,v})}{deg_u} =\frac{f_{p}+w_{p,u}}{deg_u}+\frac{\sum\limits_{v\in son(u)}(f_v+w_{u,v})}{deg_u} =\frac{f_{p}+w_{p,u}}{deg_u}+\frac{\sum\limits_{v\in son(u)}(f_v+w_{u,v})}{deg_u} =\frac{f_{p}+w_{p,u}}{deg_u}+\frac{\sum\limits_{v\in son(u)}(A_v\cdot f_u+B_v+w_{u,v})}{deg_u}

把和 f_u 相关的东西移到一起，则有：

\left( 1-\frac{\sum\limits_{v\in son(u)}A_v}{deg_u} \right)\cdot f_u = \frac{f_p}{deg_u}+\frac{w_{p,u}+\sum\limits_{v\in son(u)}(B_v+w_{u,v})}{deg_u}

可知：

f_u = \frac{1}{deg_u\cdot \left(1-\frac{\sum\limits_{v\in son(u)}A_v}{deg_u}\right)} \cdot f_p\ +\ \frac{w_{p,u}+\sum\limits_{v\in son(u)}(B_v+w_{u,v})}{deg_u\cdot \left(1-\frac{\sum\limits_{v\in son(u)}A_v}{deg_u}\right)}

因此：

A_u = \frac{1}{deg_u\cdot \left(1-\frac{\sum\limits_{v\in son(u)}A_v}{deg_u}\right)} = \frac{1}{deg_u-\sum\limits_{v\in son(u)}A_v} B_u = \frac{w_{p,u}+\sum\limits_{v\in son(u)}(B_v+w_{u,v})}{deg_u\cdot \left(1-\frac{\sum\limits_{v\in son(u)}A_v}{deg_u}\right)} = \frac{w_{p,u}+\sum\limits_{v\in son(u)}(B_v+w_{u,v})}{deg_u-\sum\limits_{v\in son(u)}A_v}

到这里，只要我们知道 f_p 的值，就能求出 f_u 的值。那么只需要以一个容易直接求得 f_u 的节点作为根即可（这个题是叶子，f_u=0）

所以，做两遍 dfs，第一遍用 A_v,B_v 求出 A_u,B_u 的值，第二遍用 f_p 求出 f_u 的值即可。