P15649

min_inf · 2026-03-08 22:23:50 · 题解

考虑对每条边求成为重边的概率。容易想到 DP 一个 f_{u,i} 表示 u 子树重链长度为 i 的概率。

考虑一个点 u 的儿子 v_1,\dots,v_k，重链长度分别是 x_1,\dots,x_k，我们如果需要 v_i 是重儿子那概率就是 \frac{x_i}{\sum x_j}。

如果只要求贡献到 \sum x 的东西的话容易直接树背包，考虑转置原理。设 g_{i,j} 为前 i 个儿子 \sum x=j 的概率，h_{i,j} 为预设了一个总和，后 i 个儿子消耗到只剩 j 的概率（乘上总和的倒数）。转移都是容易的，且时间复杂度同树背包为 \mathcal O(n^2)。

只需要 1\sim n 的逆元，不需要考虑乱七八糟的逆元问题。