BZOJ2878

• 传送门：BZOJ2878

先考虑树上的情况。

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

于是有$down(i)=\frac{\sum_{v \in S(i)} down(v)+E_{i,v}}{|S(i)|}$，$S(i)$代表i的子节点的集合。

类似的，有$up(i)=E_{i,fa(i)}+\frac{[\sum_{v \in S(fa(i))-i} down(i)+E_{fa(i),v}] +up(fa(i))}{| S(fa(i))|}$，特别的，fa(i)为根时$up(i)=E_{i,fa(i)}+\frac{[\sum_{v \in S(fa(i))-i} down(i)+E_{fa(i),v} ]}{| S(fa(i))|-1}$。

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