测试一下。
https://www.luogu.com.cn/problem/P15649
这样的题 dp 无疑。考虑确定剖分的过程肯定要明确子树重链长度,才能随重儿子。所以重链长度必须计入状态。
考虑记 $u$ 的子树重链长度为 $i$ 时,概率和答案。但是这样瓶颈在于求对于儿子 $v$,其重链长度为 $l$ 而儿子重链长度之和为 $\sum l$ 的概率。需要确定每个儿子长度,然后概率相乘,最后乘上 $\dfrac{l}{\sum l}$ 才能得到对应情况答案。
然后就不会了。
实际上首先没必要记答案,可以直接拆贡献 $ans=\sum_u P_u siz_u$,其中 $P_u$ 表示 $u$ 是轻儿子的概率。过程中会求重儿子概率,顺便累加答案即可。
树上背包确实可以快速求出 $f(u,i)$ 表示所有儿子重链长度和为 $i$ 的概率,但是无法钦定一个儿子,从而无法转移。然而可以使用回退背包删除单个儿子贡献,快速求出不考虑 $v$ 的概率。
$\ce{H2O}$