题解 CF280C 【Game on Tree】

不知道是不是有人和我一样不理解为什么每个点对答案的贡献是1/（dep+1） 所以我给一个严谨的想法（网上看的） 原问题等价于： 我们随机生成一个1～n的排列， 然后从左到右枚举点，如果没有被染黑就把它染黑，次数+1 则答案即为次数的期望（易证） 根据期望的线性性：总次数的期望=每个点被染黑次数的期望的和 由于每个点只会被染黑一次，所以求出每个点被染黑的概率即可 一个点被染黑当且仅当它的祖先结点都排在它的后面 设这个点祖先结点个数为dep（不包括本身），概率即为：1/（dep+1）