Loj#6570 毛毛虫计数

题意：毛毛虫是一棵树，满足树上存在一条链，使得树上所有点到这条树链的距离最多为 。

求 个点的有标号毛毛虫个数，答案对 取模。

，时限 。

---

休闲题。

定义毛毛虫的主链为：满足树上所有点到这条树链的距离最多为 的最短的链。

不难发现主链是唯一的，且主链上的每个点都挂了若干个节点。

于是可以将主链看成菊花组成的序列。注意，两侧的菊花至少含两个点，否则主链可以进一步缩短。

设标记了中心的菊花的组合类为 ，未标记中心的为 ，毛毛虫的组合类为 ，则有：

前半部分是主链长度 的情况，主链长度为 则对应未标记中心的菊花

改写为 EGF 的形式，则有

于是问题转化为求 。

一个大小为 的有标号菊花图，若标记了中心点，可以选任意一个点作为中心点，其余的点向根连边，于是方案数恰为 。

若未标记中心点，当 时分辨不出哪个是中心点，故方案数为 。

则 。特殊地，。

求逆+卷积可以做到 。