树上随机游走

题目：CF802L

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

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

那么对于 $\text{other cases}$：

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

可知：

因此：

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

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