AGC005F Many Easy Problems

题意：给定一棵无根树。

定义 为：对所有大小为 的点集，求能够包含它的最小连通块大小之和。

对于 分别求出 。

答案对 （质数） 取模。

，时限 。

---

妙妙题。

考虑点 对 的贡献：选出一个大小为 的点集跨越 的方案数。

对于 而言，显然只需要考虑其各个分支的大小 。

正着来有点不方便，考虑不跨越 的方案数，那么必然只能完全在一个分支内。

不合法方案数为 。总方案数为 。

设 表示 作为分支大小出现的次数，那么扣除的贡献即为 。

这个拆开组合数随便卷一卷就是了。

复杂度 。