记忆者(recoll)
题目背景
在重新拾起那些尘封的算法记忆之前，小 B 曾经做过一件很有意思的事。
那时的他刚接触树形结构，常常会把自己学过的知识点、刷过的题目、写过的代码、得到的结论，想象成一棵不断生长的“记忆树”。树上的每一个结点，都是一段具体的算法记忆；而结点之间的连边，则代表这些记忆之间的推导、启发与承接关系。
小 B 想从这棵记忆树中，整理出一个个独立的“记忆片段集合”，作为自己之后反复回味、重新找寻的珍贵线索。
题目描述
他把一次整理出的集合称作一个记忆国度。
一个记忆国度需要选择：
- 1 个核心记忆，作为这段记忆国度的“首都”；
- 若干个（也可以为 \(0\) 个）延伸记忆，它们由核心记忆直接统摄。
一段记忆国度的规模，定义为其中包含的记忆总数（包含核心记忆和所有延伸记忆）。
为了保证自己在回忆时不会“顺着一条链一路跑偏”，小 B 规定：
- 对于每一个被选作延伸记忆的结点，在从核心记忆到该结点的路径上，不能再出现其他被选作延伸记忆的结点。
换句话说，小 B 不允许某个延伸记忆，处在核心记忆与另一个延伸记忆之间；否则这两个记忆就不再是同一层级上被直接唤起的内容，而会破坏这段“记忆国度”的清晰结构。
现在，小 B 想知道：
对于每一个规模 \(k\)，一共能从这棵记忆树中整理出多少种不同的记忆国度？
两个记忆国度不同，当且仅当它们所选的核心记忆不同，或任意一个被选为延伸记忆的结点不同。
简要题意
给定一棵包含 \(n\) 个结点的无根树。
你需要统计，对于每个 \(k\ (1\le k\le n)\)，有多少种方案可以选出一个结点作为首都，并选出若干个其他结点作为次级城市，满足：
- 选出的结点总数恰好为 \(k\)；
- 对于每个次级城市，在从首都到该次级城市的简单路径上，不能出现其他次级城市。
对于每个 \(k\)，输出满足条件的方案数对 \(10^9+7\) 取模后的结果。
输入格式
第一行包含一个整数 \(n\)（\(1 \le n \le 3000\)），表示城市数量。
接下来 \(n-1\) 行，每行包含两个整数 \(u, v\)（\(1 \le u, v \le n\)，\(u \ne v\)），表示城市 \(u\) 与 \(v\) 之间有道路。
输出格式
输出一行包含 \(n\) 个整数，分别表示规模为 \(1,2,\dots,n\) 的国家数量对 \(10^9+7\) 取模的值。
输入输出样例 #1
输入 #1
4
1 2
1 3
1 4
输出 #1
4 12 6 1
输入输出样例 #2
输入 #2
4
1 2
2 3
1 4
输出 #2
4 12 4 0
说明/提示
【样例解释】
样例 #2 解释：
- 规模为 \(1\)：只有选首都，因此共 \(4\) 种方案。
- 规模为 \(2\)：先选首都（\(4\) 种），再选 \(1\) 个次级城市（剩下 \(3\) 种），因此共 \(12\) 种方案。
- 规模为 \(3\)：当首都选 \(1\) 或 \(2\) 时，各有 \(2\) 种方案选择 \(2\) 个次级城市，因此共 \(4\) 种方案。
【子任务】
| 子任务 | 分值 | 限制 |
|---|---|---|
| \(1\) | \(18\) | \(1 \le n \le 15\) |
| \(2\) | \(17\) | \(1 \le n \le 200\) |
| \(3\) | \(26\) | \(1 \le n \le 600\) |
| \(4\) | \(49\) | 无额外限制 |