很有趣的题,没想到NTT的解法,看了以后感觉很有启发性,  ,思路挺自然,难点在于状态设计和NTT这里着重说一下偏向问题转化的  解法根据期望的线性可加性,  即每个点期望选中次数的和,并且每个点是独立的,所以可以独立考虑.现在的规则是只能选坏点,然后计数.那我们如果好点和坏点都可以选,选中好点不计数是不是也一样(这样对于每个坏点被选的概率还是相同的对吧)直到这个点变为好点(即他到根的链全被选完了)那他以后再也不可能计数了对吧,  表示第k次选中了x这个点且在之前x还是坏点的概率.显然  ,根据容斥原理算Pd为x到根上点的个数,这个容斥就是强制至少有i个路径上的点没有被选.
由定义和等比数列得到观察到每个E(x)只跟d有关,那就先差分化简再前缀和,把组合数变变形,把求和换一换,很trivial所以答案就是所有点的深度的调和级数的和