Description

Link：CF1111E

Solution

考虑计数。设 $c_1, c_2, \cdots, c_k$ 分别表示 $a_1, a_2, \cdots, a_k$ 到根节点 $r$ 的路径上有多少个关键点。则将 $k$ 个关键点分进至多 $m$ 个有标号组的方案数为

$$f(m) = \prod_{i = 1}^k (m - c_i)$$

但由于组与组之间不区分（无标号），设 $g(m)$ 表示将 $k$ 个关键点分进恰好 $m$ 个有标号组的方案数，则答案应为 $\sum_{i = 1}^n \frac{g(i)}{i!}$。

由二项式反演

$$f(i) = \sum\limits_{j = 1}^i \binom{i}{j} g(j) \iff g(i) = \sum\limits_{j = 1}^i (-1)^{i - j} \binom{i}{j} f(j)$$

故先求出 $f(i)$，再通过二项式反演求出 $g(i)$，最后计算 $\sum_{i = 1}^n \frac{g(i)}{i!}$ 即可。

至于 $c_i$ 的处理，可以在 dfs 序上使用树状数组维护，并使用换根 Trick。

时间复杂度 $\mathcal{O}(\sum k \log n + \sum km)$。