$n \le 8$
最朴素的暴力法可过，通过搜索所有剖分方案并计算期望即可。
$n \le 20$
可以将问题转化为枚举重儿子的选择，由于每条边都有可能被选为重边，直接枚举的复杂度不超过 $O(2^n)$。
特殊性质 A
对于链形结构，任何结点都没有轻边，直接输出 $0$ 即可。
$n \le 500$ 与特殊性质 B
问题中的难点在于，结点的重儿子选择概率与其子结点所在重链的长度（即 $\sum l_i$ 的比例）相关。因此，需要在 DP 状态中记录对应的信息。
设 $f_{u,k}$ 表示结点 $u$ 所在的子树中，包含 $u$ 的重链长度为 $k$ 的概率。为了计算状态转移，需要维护所有子树的重链长度之和，这可以转换为一个背包问题。
对于结点 $u$ 的子树，设 $g_{i,j}$ 表示当前包含 $u$ 的重链长度为 $i$，且所有参与分配的子结点所在重链长度之和为 $j$ 的概率或方案数。在合并子树 $v$ 时，分别考虑 $v$ 是否被选为 $u$ 的重儿子：
- 若指定 $v$ 为重儿子，则 $u$ 所在重链的长度将增加 $v$ 所在重链的长度：$g_{i,j} \leftarrow g_{i,j} + g_{0,j-i} \times f_{v,i}$；
- 若 $v$ 为轻儿子，则 $u$ 所在重链长度不变，但总重链长度之和增加：$g_{i,j} \leftarrow g_{i,j} + g_{i,j-k} \times f_{v,k}$。
在所有子树合并完毕后，可以计算出 $f_{u,k}$ 的值：$f_{u,k} = \sum_{j=k}^n \frac{g_{j,k}}{j}$。计算这部分状态的复杂度为 $O(n^3)$。
接下来考虑如何计算答案。可以采用类似的 DP 来维护期望和对答案的贡献。对于子结点 $w$，只要它不被选为重儿子，其所在的子树在 $u$ 这一层就会产生 $siz_w$ 的轻边期望贡献。也就是说，如果指定 $v$ 为重儿子，当前层产生的轻边代价总计为 $siz_u - 1 - siz_v$。
设 $h_{i,0/1}$ 表示当前所有子结点重链长度之和为 $i$，且是否已经选定过重儿子（$1$ 表示已选，$0$ 表示未选）的贡献之和。
- 选择 $v$ 作为重儿子，则累加其余轻儿子产生的代价：$h_{i,1} \leftarrow h_{i,1} + h_{i-j,0} \times f_{v,j} \times (siz_u - 1 - siz_v)$；
- $v$ 不作为重儿子，则仅发生背包合并：$h_{i,0} \leftarrow h_{i,0} + h_{i-j,0} \times f_{v,j}$。
在子树转移完成后，对于结点 $u$，向最终答案中累加 $\sum_{i} \frac{h_{i,1}}{i}$ 即可。这部分的合并复杂度为 $O(n^2)$。综合起来，得到一个复杂度为 $O(n^3)$ 的算法。
事实上，由于状态的第二维受限于最大深度，复杂度的上界也是 $O(nh^2)$，其中 $h$ 为树高。因此这一算法也可以通过特殊性质 B 的部分分。
$n \le 1500$
若采用多项式乘法（NTT）优化背包合并过程可以达到更好的复杂度。
$n \le 5000$
为了优化上述第一部分时间复杂度为 $O(n^3)$ 的求 $g$ 过程，考虑调整合并的策略。
若不考虑具体选择哪条重链，仅维护各个子树产生的重链总长度，这就退化为了一个平凡的 $O(n^2)$ 树形背包问题。设这个状态为 $g_0$。对于 $g$，若选定一个子树 $v$ 作为重儿子，其实质就是除了 $v$ 之外，其它子树合并后的普通背包 $g'_0$，再与 $v$ 自己的 $f_v$ 合并的结果，即 $g_{i,j} \leftarrow g_{i,j} + g'_{0,j-i} \times f_{v,i}$。
考虑如何快速得到排除掉 $v$ 后的背包状态 $g'_0$。注意到普通背包 $g_0$ 的合并是无序的，因此可以从最终的 $g_0$ 中撤回子树 $v$ 的贡献： 对于总长度限制 $s_j$，撤销操作可以表示为：$g'_{0,i} = g_{0,i} - \sum_{j=1}^{\min(i-1, s_j)} g'_{0,i-j} \times f_{v,j}$。
改进合并与撤销流程后，对于结点 $u$，设其所有儿子 $v_1, v_2, \dots, v_k$ 的最大深度（即 $s$）之和为 $S$。对于单个儿子 $v_k$ 的撤销与重算过程，其操作次数约为 $(S - s_{v_k}) \times s_{v_k}$。借助树形背包的经典复杂度分析，项 $(S - len_{v_k}) \times len_{v_k}$ 的组合意义等价于 $v_k$ 内的最长链与 $u$ 其它儿子的最长链两者之间的所有结点两两配对。由于树上最长链内的结点之间最多只会被配对计算一次，全局的总时间复杂度为 $O(n^2)$。
另外，还有一个直观的优化方案：使用长链剖分进行优化。将长儿子放在最后加入 DP，那么在它之前已经得到了其余儿子所构成的 $g'_0$，直接进行正常的 DP 即可，避免了对它的撤销操作。而在不进行撤销操作的前提下，按照普通的树形背包合并的复杂度分析，这一过程严格限定在 $O(n^2)$。