自动搬运

查看原文

来自洛谷，原作者为

	E1_de5truct0r 若梦尽欢时

搬运于2025-08-24 22:47:33，当前版本为作者最后更新于2023-05-20 20:16:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

盯着想了好一会儿的。主要是一开始不太知道从哪里下手好，以后还是要提高抓关键的能力。。。

这道题还是一个不错的树形背包题的。

---

Part I 转化条件

不难发现，每个点度数不超过 $2$ 这个条件，和把一个树剖成若干条链是等价的。

首先一步转化。观察到求第一次成为凋零状态并不好做，因为会重复。因此考虑容斥掉这个限制条件。

具体地，假设 $dp_i$ 表示断掉 $i$ 条边，第一次成为凋零状态的答案，$f_i$ 表示断掉 $i$ 条边，成为凋零状态的答案。考虑是否可以递推，不难发现如果在求 $dp_i$ 的时候我们已经求出了 $dp_1,dp_2,\dots,dp_{i-1}$，所以我们可以直接用 $f_i-\sum_{j=1}^{i-1} dp_j$ 求。所以直接做就可以了。

那么问题就转化为怎么求凋零状态方案数了。

---

Part II 解决问题

考虑当前节点 $u$，一共三种可能：

• 和它的儿子没有连边

• 和它的儿子有 $1$ 条边

• 和它的儿子有 $2$ 条边

考虑 DP：$f_{i,j,k}$ 表示第 $i$ 个节点为根的子树内，断开 $j$ 条边之后，状态为 $k$（$k \in \{0,1,2\}$）且凋零的方案数。

考虑从儿子 $v$ 转移到父亲 $i$，无非是断开 / 不断开这条边。

• 断开：$f_{i,j,k}$ 的 $k$ 状态不变。需要在背包的时候扣掉一步用来断掉这条边。

• 保留：$f_{i,j,k}$ 的 $k$ 状态会变大 $1$。这时背包转移是不需要留出这一步的。

而我们不难发现，转移之后的概率为 $i$ 和 $v$ 分配到了各自的步数之后，都成为“凋零”状态的概率乘起来。

为了避免后效性，应把 $f_{i,j,k}$ 拆到 $t_{j,k}$ 里转移，再赋值回去。不过我比较懒就统一使用 $f$ 了。。。

转移方程：

$$\begin{cases}f_{i,j,0}=\sum_{k} f_{i,j-k-1,0} \times (f_{v,k,0}+f_{v,k,1}+f_{v,k,2})\\f_{i,j,1}=\sum_{k} f_{i,j-k-1,1} \times (f_{v,k,0}+f_{v,k,1}+f_{v,k,2})\\f_{i,j,2}=\sum_{k} f_{i,j-k-1,2} \times (f_{v,k,0}+f_{v,k,1}+f_{v,k,2})\\f_{i,j,1}=\sum_{k}f_{i,j-k,0} \times (f_{v,k,0}+f_{v,k,1})\\f_{i,j,2}=\sum_{k}f_{i,j-k,1} \times (f_{v,k,0}+f_{v,k,1})\end{cases} $$

---

Part III 得出答案

最后对每个 $j$，拿 $\sum_{k \in \{0,1,2\}}f_{1,j,k}$ 作为 $f_j$ 然后按上文（Part I 中）所述的方法，容斥出来最后的答案数组 $dp_j$。

不难发现期望就是概率乘步数。所以输出 $\sum dp_{i} \times i$ 即可。

复杂度 $O(n^2)$。

---

Part IV 小结

期望题如果贡献的范围小（或者步数是可接受范围），考虑拆成概率和贡献相乘。

对关键词要敏感。善用容斥。

树形背包的关键在于父亲和儿子之间的转移。特点是转移过程中是一棵空树到完整的树的子树添加过程。这可以避免产生后效性。

比较复杂的题目最好使用刷表法写树形背包，一般情况下都比查表好写的多（边界少）。虽然这题我也没用刷表，但介于这题码量还行就硬撑了。