GDOI2026 邮寄

首先想了一个猎奇求重链期望长度的算法，但是复杂度 $O(n)$，看一眼 $n \le 5000$ 立马丢了。

然后想到先拆贡献，转成每条边为轻链的概率乘下面那个点的子树的 $siz$，那么对于一个 $u$，假设他有 $m$ 个儿子 $0,1,2,...,m-1$（为了公式编辑方便一些），那么对于一条 $(u,v)$ 的边，它的贡献为：

其中 $slen_u$ 表示 $u$ 的儿子的 $l$ 之和，$f_{i,j}$ 表示 $i$ 所在的重链目前长度为 $j$ 的概率，后面那个连乘就是当前这个 $l$ 序列的概率。

首先枚举一个 $l_v$，然后对着这个柿子看了半天后发现 $slen_u-l_v$ 这个东西好像也可以再枚举，复杂度也是对的。

然后这个玩意就简单了，只需要知道所有合法 $l$ 序列的后面那个连乘的结果的和就行了，由于我们枚举的 $slen_u-l_v$ 相当于是 $u$ 的儿子长度序列中扣掉了一个 $l_v$，所以我们要算出扣掉 $v$ 后的序列的概率，这个东西可以退背包或者搞个前后缀后合并两边。

最后的柿子就是：

其中 $d_{v,j}$ 表示扣掉 $v$ 之后的 $slen_u=j$ 的合法 $l$ 序列的概率的和。

$f$ 和 $d$ 都用树上背包转移就行了，$f$ 的转移和 $ans$ 的很像。

这题终于结束了，共用 1.5h。