题目描述

对于一颗树,每次随机选择一个叶子,将其染黑,经过无数次操作以后,所有叶子将变成黑色。求期望在这之前的哪一时刻,不包含黑色点的直径长度第一次变小?

思路

首先我们找到这棵树的直径。如果直径长度是偶数,所有直径必有一个必经点,这个点为中点;如果直径长度是奇数,所有直径必有一条必经边,这条边也在直径的正中间。

我们沿着必经点或者必经边切开,能把树分成若干个集合,每个集合中有一些叶子是直径可能的端点。直径长度变小,当且仅当除剩下的一个集合外,所有集合中可能作为直径端点的叶子均被染黑。

于是我们可以枚举剩下哪个集合没有被全部染黑,分别计算贡献,最后容斥一下得出答案。

代码