CF1517F Reunion

题意：给出一棵 个节点的树，每个节点有 的概率为白色， 的概率为黑色。

求纯黑邻域的最大半径的期望，答案对 取模。

，时限 。

---

发现计算最大邻域较为困难（因为条件是或起来的），正难则反，考虑对每个 计算邻域大小 的方案数。

等价于每个点的最近白点的距离都 ，即每个白点能覆盖距离 内的点，需要覆盖整棵树的方案数。

记 表示：

• ： 的子树内完全覆盖，且还能像子树外延伸 的距离。

• ： 的子树内未被覆盖的最远点距离 为 。

答案为 。

转移：考虑加入 的直接儿子 。

先只考虑 点为黑色的情况 ：

在所有转移完毕后，再考虑 点为白色的情况。令 加上 的总和。

注意到 中 的可能取值个数为 ，则根据树形背包的复杂度分析，复杂度为 。

次 DP 则 ，可以通过。