随机走,看期望
由于zzn过于sb,考试推出来式子因为统计时间不对没有$AC$(应dfs前统计)
zzn实在过于sb,式子和题解完全不一样,所以看题解的可以走了
记录tofa[x]表示当前点走到父亲期望步数
可以直接走到父亲 贡献$\frac{1}{deg[x]}$
走到儿子再走到父亲$\frac{1}{deg[x]}*(1+tofa[y]+tofa[x]) $解释一下,花一步走到$y$,花$tofa[y]$走到$x$最后还是要走到$fa$
总$tofa[x]=\frac{1}{deg[x]}+\sum\limits_{y}^{y\in son[x]} \frac{1}{deg[x]} (1+tofa[y]+tofa[x])$
记录toson[x]表示从父亲走到x步数
考虑toson[y]转移
从$x$直接走到$y$ $\frac{1}{deg[x]}$
走到$x$父亲再走到$y$ $\frac{1}{deg[x]}*(toson[x]+1+toson[y])$
走到$y$兄弟走到$y$ $\frac{1}{deg[x]}*(1+tofa[y]+toson[y])$
总$toson[y]=\frac{1}{deg[x]}+\frac{1}{deg[x]}*(toson[x]+1+toson[y]) +\sum\limits_{y2}^{y2\in son[x] \& y2!=y} *(1+tofa[y2]+toson[y])$
然后移项
$tofa[x]=deg[x]+\sum\limits_{y}^{y\in son[x]}tofa[y]$
$toson[y]=deg[x]+toson[x]+\sum\limits_{y2}^{y2\in son[x] \& y2!=y} tofa[y2]$
原文：https://www.cnblogs.com/znsbc-13/p/11586409.html