[DP记录]CF1517F Reunion

**题意** ： 给出一棵 $n$ 个节点的树，每个节点有 $\frac{1}{2}$ 的概率为白色， $\frac{1}{2}$ 的概率为黑色。 求纯黑邻域的最大半径的期望，答案对 $998244353$ 取模。 $n\leq 300$ ，时限 $\texttt{3s}$。 ------------ 发现计算**最大**邻域较为困难（因为条件是或起来的），正难则反，考虑对每个 $L$ 计算邻域大小 $<L$ 的方案数。 等价于每个点的最近白点的距离都 $\leq L$ ，即每个白点能覆盖距离 $\leq L$ 内的点，需要覆盖整棵树的方案数。 记 $f[u][k]$ 表示 : - $k\geq 0$ : $u$ 的子树内完全覆盖，且还能像子树外延伸 $k$ 的距离。 - $k<0$ : $u$ 的子树内未被覆盖的最远点距离 $u$ 为 $k-1$ 。 答案为 $\sum_{k\geq 0} f[1][k]$ 转移 ： 考虑加入 $u$ 的直接儿子 $v$。 先只考虑 $u$ 点为黑色的情况 ： - $k_1,k_2<0$ $$f[u][k_1]f[v][k_2]\rightarrow f'[u][\min(k_1,k_2-1)]$$ - $k_1<0,k_2\geq 0,k_1+k_2\geq 0$ $$f[u][k_1]f[v][k_2]\rightarrow f'[u][k_2]$$ - $k_1<0,k_2\geq 0,k_1+k_2<0$ $$f[u][k_1]f[v][k_2]\rightarrow f'[u][k_1]$$ - $k_1\geq 0,k_2<0,k_1+k_2\geq 0$ $$f[u][k_1]f[v][k_2]\rightarrow f'[u][k_1]$$ - $k_1\geq 0,k_2<0,k_1+k_2<0$ $$f[u][k_1]f[v][k_2]\rightarrow f'[u][k_2]$$ - $k_1,k_2\geq 0$ $$f[u][k_1]f[v][k_2]\rightarrow f'[u][\max(k_1,k_2-1)]$$ 在所有转移完毕后，再考虑 $u$ 点为白色的情况。 则 $f[u][L]$ 加上 $f[u][\_]$ 的总和。 注意到 $f[u][k]$ 中 $k$ 的可能取值个数为 $O(siz_u)$ ，则根据树形背包的复杂度分析，可以做到 $O(n^2)$。 $n$ 次 DP 则 $O(n^3)$ ，可以通过。 ```cpp ```