社区讨论

求助假做法

P5643[PKUWC2018] 随机游走参与者 4已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@lo99rn08
此快照首次捕获于
2023/10/28 07:53
2 年前
此快照最后确认于
2023/10/28 07:53
2 年前
查看原帖
首先变成给一堆终点,求第一次到达某个终点时的步数。
从某个非根节点 uu 开始游走有两种情况:先到达某个终点,或先到达父亲。
fuf_u 为假定第一种情况发生的前提下,第一次到达某个终点的期望步数,乘以第一种情况发生的概率。也就是说所有第一种情况的结果中步数乘以发生概率之和。
gug_u 为假定第二种情况发生的前提下,第一次到达父亲的期望步数,乘以第二种情况发生的概率;huh_u 为第二种情况发生的概率。 fu=1duv1+fv+gv+hvfuf_u=\frac1{d_u}\sum_v1+f_v+g_v+h_vf_u gu=1du+1duvgv+hv+hvgug_u=\frac1{d_u}+\frac1{d_u}\sum_vg_v+h_v+h_vg_u hu=1du+1duvhvh_u=\frac1{d_u}+\frac1{d_u}\sum_vh_v vvuu 的儿子,dud_uuu 的度数(包括父亲)。
这个做法是假的,比如造一条四个点的链,最下面那个点是终点,那从上往下第二个点的 gg 应该是 11,但是按这个式子算出来是 43\dfrac43
求问哪里假了。

回复

11 条回复,欢迎继续交流。

正在加载回复...