CF1707D Partial Virtual Trees

河城荷取是一个热爱竞赛编程的少女。一天，她发现了一棵有 $n$ 个结点的有根树，根为结点 $1$。作为一名高级出题人，她很快想到了一个问题。 河城荷取有一个结点集合 $U=\{1,2,\ldots,n\}$。她准备用这棵树和这个集合玩一个游戏。每次操作时，她会选择一个结点集合 $T$，其中 $T$ 是 $U$ 的一个部分虚树，并将 $U$ 变为 $T$。 如果结点集合 $S_1$ 是结点集合 $S_2$ 的一个部分虚树，则 $S_1$ 是 $S_2$ 的真子集，且对于 $S_1$ 中的任意两个结点 $i$ 和 $j$，都有 $ \operatorname{LCA}(i,j) $ 也在 $S_1$ 中，其中 $ \operatorname{LCA}(x,y) $ 表示树上结点 $x$ 和 $y$ 的最近公共祖先。注意，一个结点集合可能有多个不同的部分虚树。 河城荷取想知道，对于每一个可能的 $k$，如果她恰好进行了 $k$ 次操作，最终能有多少种不同的方法使得 $U=\{1\}$？如果存在某个整数 $z$（$1 \le z \le k$），使得第 $z$ 次操作后 $U$ 不同，则认为两种方法是不同的。 由于答案可能非常大，你需要输出对 $p$ 取模的结果。保证 $p$ 是一个质数。

第一行包含两个整数 $n$ 和 $p$（$2 \le n \le 2000$，$10^8 + 7 \le p \le 10^9+9$）。保证 $p$ 是一个质数。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示 $u_i$ 和 $v_i$ 之间有一条边。 保证给定的边构成一棵树。

输出一行共 $n-1$ 个整数，依次表示 $k=1,2,\ldots,n-1$ 时的答案对 $p$ 取模后的结果。

在第一个测试点中，当 $k=1$ 时，唯一的方案是： 1. $ \{1,2,3,4\} \to \{1\} $。 当 $k=2$ 时，有 $6$ 种方案： 1. $ \{1,2,3,4\} \to \{1,2\} \to \{1\} $； 2. $ \{1,2,3,4\} \to \{1,2,3\} \to \{1\} $； 3. $ \{1,2,3,4\} \to \{1,2,4\} \to \{1\} $； 4. $ \{1,2,3,4\} \to \{1,3\} \to \{1\} $； 5. $ \{1,2,3,4\} \to \{1,3,4\} \to \{1\} $； 6. $ \{1,2,3,4\} \to \{1,4\} \to \{1\} $。 当 $k=3$ 时，有 $6$ 种方案： 1. $ \{1,2,3,4\} \to \{1,2,3\} \to \{1,2\} \to \{1\} $； 2. $ \{1,2,3,4\} \to \{1,2,3\} \to \{1,3\} \to \{1\} $； 3. $ \{1,2,3,4\} \to \{1,2,4\} \to \{1,2\} \to \{1\} $； 4. $ \{1,2,3,4\} \to \{1,2,4\} \to \{1,4\} \to \{1\} $； 5. $ \{1,2,3,4\} \to \{1,3,4\} \to \{1,3\} \to \{1\} $； 6. $ \{1,2,3,4\} \to \{1,3,4\} \to \{1,4\} \to \{1\} $。 由 ChatGPT 4.1 翻译