P9346

· · 题解

前言

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

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

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，一共三种可能：

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

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

而我们不难发现，转移之后的概率为 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 小结

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

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

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

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