对于这种情况,贡献期望长度当然为:
最后即可得到式子:
这个式子很好懂,但是能不能更加简单呢?
由这个式子,我们可以得到每个节点到父亲节点的期望距离.同时我们观察这个式子,它的意思是,当前节点的 \(f\) 值为所有儿子的 \(f\) 值之和加上它的度数.那么我们来思考一下:
那么我们再仔细端详这个式子:
那么这个式子就可以变为:
那幺子树内 \(d[i]\) 的和,我们就可以理解为计算边的贡献.由于子树内的边必定都连接着子树内的点,则每条边都为子树内的每个点的度数之和增加了 \(2\) 的贡献.而子树内的边数为 \(size[i]-1\) ,即每个节点向父亲都有且仅有一条边,那幺子树内的边的贡献值和为:\((size[i]-1)*2\)
也可以写成:
对于第一条路径,肯定是全程向上的,对于第二条路径,肯定是全程向下的.
那么长度肯定为: