P14780 [COCI 2025/2026 #3] 国家 / Drzava

本题满分 $110$。

在遥远的 Airlanvaosma-i 国度，有 $n$ 座城市，由 $n-1$ 条道路连接，且从任意城市到任意城市都能到达。并且任意两座城市之间的最短路经过的道路数都小于 $36$。 Krešimir 想建立自己的国家。一个国家必须选择： - $1$ 个**首都**（从这里治理国家）； - 若干个（可以为 $0$ 个）**次级城市**（归首都管辖）。 国家的规模定义为该国家包含的城市总数（包含首都和所有次级城市）。 为了保证治理效率，Krešimir 规定： - 对每一个次级城市，在从首都到该次级城市的路径上，**不能出现其他次级城市**。 换句话说：不允许某个次级城市位于首都与另一个次级城市之间。 对每个规模 $k$（$1 \le k \le n$），求 Krešimir 能建立多少个不同规模为 $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$ 取模的值。

#### 【样例解释】 样例 #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$ | 无额外限制 |