[关闭]
@Jerusalem 2015-11-22T07:58:20.000000Z 字数 562 阅读 1237

BZOJ2878



先考虑树上的情况。

首先我们将树有根化,定义状态down(i),代表从i出发,第一步走其子节点的期望长度,状态up(i),代表从i出发,第一步走其父节点的期望长度。

于是有down(i)=vS(i)down(v)+Ei,v|S(i)|S(i)代表i的子节点的集合。

类似的,有up(i)=Ei,fa(i)+[vS(fa(i))idown(i)+Efa(i),v]+up(fa(i))|S(fa(i))|,特别的,fa(i)为根时up(i)=Ei,fa(i)+[vS(fa(i))idown(i)+Efa(i),v]|S(fa(i))|1

接下来考虑环,我们可以枚举环上的点,暴力统计其up值。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注