← 返回比赛

已结束 KTXY Round 1

← 上一题下一题 →

A7216 | $今乘霄\cdot夕共圆$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

题目背景 逐光取月夕流光，惊龙破空岁凌霄 >神霓飞芒浮光寒，韶华共济溯清辉 >沉海洄天溯，绒雪凝屏息；天定神子身，自甘佑凡尘；流光化霜雪，寒尽又逢春。 题目描述 今汐会给定你一个大小为 $n$ 的无根树。你可以在上面选择一个点作为中枢信标，并选择若干个点作为小型信标。 要求对于每一个小型信标，其到中枢信标的路径上不能出现其他小型信标。换句话说，不允许一个小型信标出现在其他小型信标到中枢信标的路径上。 令一种选择方式的规模为信标总个数，即小型信标个数加上中枢信标个数。 今汐想请你求出对于每个 $k \in [1,n]$，有多少规模为 $k$ 的树。 两棵树的选择方案不同。当且仅当其中枢信标不同或者任一小型信标不同。 保证数据随机，具体随机方式见提示说明。

输入格式

第一行包含一个正整数 $n$，表示树的大小。 接下来 $n-1$ 行，每行包含两个正整数 $u,v(1 \le u,v \le n,u \ne v)$，表示 $u,v$ 两点之间有一条边连接。

输出格式

输出一行包含 $n$ 个整数，分别表示规模为 $1,2,3,\cdots$ 的树个数。 由于答案可能很大，请将答案对 $10^9+7$ 取模。

输入输出样例

输入 #1

输出 #1

4 12 4 0

输入 #2

输出 #2

5 20 10 0 0

子任务分值限制$1$$10$$1 \le n \le 15$$2$$20$$1 \le n \le 200$$3$$30$$1 \le n \le 600$$4$$40$$1 \le n \le 3000$ 本题数据随机，具体的，一个点 $i(i>1)$ 会与 $[1,i-1]$ 中的随机一个点进行连边。

C++ 编辑器

输入

输出