U536130 【搬运】marco.wav

$400^2$ 给三秒过分了。

micro.wav（以下简称 MW）正在和 macro.wav（以下简称 MW）玩游戏。 MW 有一棵 $n$ 个点的无根树 $T$。她想做若干次操作将 $T$ 删空。 每次操作是选择至少一个未被删去的点，然后将这些点以及它们的邻边删去。每次操作后，它都希望 $T$ 仍然是连通的。 当 $T$ 中没有节点时，MW 会停止操作。 对于每个 $k ∈ [1, n]$，MW 想知道有多少种符合条件的删除方案，使得这种方案中进行了**恰好** $k$ 次操作。 为了方便，你只需要告诉 MW 答案模 $10^9+7$ 的结果。

第一行，一个正整数 $n$。 接下来 $n − 1$ 行，每行两个正整数 $u, v$，表示 T 中的一条边 $(u, v)$。

$n$ 行，每行一个非负整数，其中第 $k$ 行表示进行 $k$ 次操作将树删空的方案数模 109 + 7 的值。

共 $40$ 个测试点，五个测试点一个子任务。 随机数据不保证强度。 | 测试点 | $n$ | 分数 | |:-:|:-:|:-:| |$1\sim5$ | $=20$ | 10 | |$6\sim10$ | $=400$ | 10 | |$11\sim15$ | $=1000$ | 10 | |$16\sim20$ | $=2000$ | 14 | |$21\sim25$ | $=3000$ | 14 | |$26\sim30$ | $=4000$ | 14 | |$31\sim35$ | $=5000$ | 14 | |$36\sim40$ | $=6000$ | 14 |