题解：P9346 无可奈何花落去

· · 题解

前言

由于是集训题所以根据标题可知这是一道树形DP 但是前面有一堆关于期望的转化而且集训的PPT上没有详细过程，所以来写一篇

题意

给定含有 n 个点的树，每单位时间会随机断开一条边，求使得树变为若干条链的期望时间。答案对 985661441 取模。

n \le 5\times 10^3

思路

首先我们注意到度数约束：设节点 i 的初始度数为 d_i，为了使其最终度数\le 2，需要断开至少 \max (0, d_i-2) 条边。记 r_i =\max (0, d_i-2)，这是节点 i 必须断开的最小边数，也就是约束。

期望凋零时间可以表示为所有可能断边顺序中首次满足凋零条件的时间的平均值。我们可以通过计算每个可能的凋零时间 k 的概率，然后求和得到期望（期望的定义）。

首先我们来看一下期望的式子（对于本题而言）：

E = \sum_{k=0}^{n-1} k \cdot P(\text{首次在第k天凋零})

我们考虑拆开计算，我们需要确定对于每个 k，断 k 条边后首次满足凋零条件的方案数，这涉及到组合计数和容斥原理的应用。

直接计算满足约束的边集数量较难，因此用容斥原理转化为 “减去不满足约束的情况”。

我们很容易得到方案数（用 C(k) 表示）的计算公式：

C(k) = \sum_{S \subseteq V} (-1)^{|S|} \cdot N(S, k)

其实这只是套话 ::::info[简单地] 所有的减不满足约束的等于满足约束的 ::::

所以以这个思路我们就可以将问题转换为求解断开 i 条边使得树变为若干条链的方案数，就得到了 PPT 上轻描淡写的一句

所以我们可以直接树形 DP，设 dp[i][j][k] 表示子树 i 内断开 j 条边且节点 i 连接 0/1/2 条边的方案，等价于树形背包，直接做即可。

得到 C(k) 后，我们需要计算所有可能的断边顺序中，恰好第 k 天首次凋零的方案数。这可以通过以下步骤实现：

  1. 计算 S(k)：断 k 条边后凋零的所有排列数。S(k) = C(k) \times k! \times (n-1 - k)!，这里 k! 是前 k 步断边的排列数，(n-1 -k)! 是剩余边的排列数。

  2. 计算首次凋零的方案数：f(k) = S(k) - S(k-1)，其中 S(-1) = 0。

  3. 计算期望：E = \frac{\sum_{k=0}^{n-1} k \cdot f(k)}{(n-1)!}