Description：

一棵 $n$ 个点的树，设 $f(k)$ 表示有多少个大小为 $k$ 的点集，使得所有点都在一条链上的方案数，求 $f(1)\sim f(n)$ 。

$1\leqslant n\leqslant 10^5$

Solution：

看上去这种输出 $f(1)\sim f(n)$ 的就大概率 $FFT$ 了，首先直接计数点集肯定是很不好做的，于是考虑枚举链，为了保证计数不重不漏可以保证链的两端点必须都是选了的点，那么我们可以先用点分治 $+FFT$ 预处理出 $g[l]$ 表示长度为 $l$ 的路径条数，然后答案就是： $$ ans[k]=\sum_{l=k - 2}^ng[l]\times \binom{l-2}{k-2}=\sum_{l=k-2}^n\frac{g[l]\times (l-2)!}{(k-2)!(l-k)!} $$ 不难发现是一个卷积，于是 $FFT$ 就好了。

Code：

没有代码