保定网站建设方案报价,个人网站备案内容不合格,网站是怎么做出来的,设计图案随机走,看期望 由于zzn过于sb,考试推出来式子因为统计时间不对没有$AC$(应dfs前统计) zzn实在过于sb,式子和题解完全不一样,所以看题解的可以走了 记录tofa[x]表示当前点走到父亲期望步数 可以直接走到父亲 贡献$\frac{1}{deg[x]}$ 走到儿子再走到父亲$\frac{1}{deg[x]}*(1tofa… 随机走,看期望 由于zzn过于sb,考试推出来式子因为统计时间不对没有$AC$(应dfs前统计) zzn实在过于sb,式子和题解完全不一样,所以看题解的可以走了 记录tofa[x]表示当前点走到父亲期望步数 可以直接走到父亲 贡献$\frac{1}{deg[x]}$ 走到儿子再走到父亲$\frac{1}{deg[x]}*(1tofa[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]} (1tofa[y]tofa[x])$ 记录toson[x]表示从父亲走到x步数 考虑toson[y]转移 从$x$直接走到$y$ $\frac{1}{deg[x]}$ 走到$x$父亲再走到$y$ $\frac{1}{deg[x]}*(toson[x]1toson[y])$ 走到$y$兄弟走到$y$ $\frac{1}{deg[x]}*(1tofa[y]toson[y])$ 总$toson[y]\frac{1}{deg[x]}\frac{1}{deg[x]}*(toson[x]1toson[y]) \sum\limits_{y2}^{y2\in son[x] \ y2!y} *(1tofa[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
