AT_abc207_f [ABC207F] Tree Patrolling

有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1$ 到 $N$。第 $i$ 条边连接了顶点 $u_i$ 和顶点 $v_i$，且为双向边。 你作为这棵树的主人，打算在若干个顶点（可以为 $0$ 个）上选择放置高桥君，让他来守卫这棵树。被放置在顶点 $x$ 的高桥君会守卫顶点 $x$ 以及所有与 $x$ 直接通过边相连的顶点。 选择放置高桥君的顶点的方式共有 $2^N$ 种。在这些方式中，有多少种方式使得被至少一位高桥君守卫的顶点恰好有 $K$ 个？ 请对于 $K=0,1,\ldots,N$，分别输出答案，并对 $10^9+7$ 取模。

输入以如下格式从标准输入读入。 > $N$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\hspace{0.6cm}\vdots$ > $u_{N-1}$ $v_{N-1}$

请输出 $N+1$ 行。第 $i$ 行输出当 $K=i-1$ 时的答案。

### 限制条件 - $1 \leq N \leq 2000$ - $1 \leq u_i < v_i \leq N$ - 给定的图为一棵树 - 输入均为整数 ### 样例说明 1 放置高桥君的顶点选择方式共有如下 $8$ 种： - 不在任何顶点放置高桥君。此时所有顶点都未被守卫。 - 只在顶点 $1$ 放置高桥君。此时所有顶点都被守卫。 - 只在顶点 $2$ 放置高桥君。此时顶点 $1$ 和 $2$ 共 $2$ 个顶点被守卫。 - 只在顶点 $3$ 放置高桥君。此时顶点 $1$ 和 $3$ 共 $2$ 个顶点被守卫。 - 在顶点 $1$ 和顶点 $2$ 放置高桥君。此时所有顶点都被守卫。 - 在顶点 $1$ 和顶点 $3$ 放置高桥君。此时所有顶点都被守卫。 - 在顶点 $2$ 和顶点 $3$ 放置高桥君。此时所有顶点都被守卫。 - 在所有顶点都放置高桥君。此时所有顶点都被守卫。 由 ChatGPT 4.1 翻译