CF1707D.Partial Virtual Trees

Kawashiro Nitori is a girl who loves competitive programming. One day she found a rooted tree consisting of $n$ vertices. The root is vertex $1$. As an advanced problem setter, she quickly thought of a problem.

Kawashiro Nitori has a vertex set $U={1,2,\ldots,n}$. She's going to play a game with the tree and the set. In each operation, she will choose a vertex set $T$, where $T$ is a partial virtual tree of $U$, and change $U$ into $T$.

A vertex set $S_1$ is a partial virtual tree of a vertex set $S_2$, if $S_1$ is a subset of $S_2$, $S_1 \neq S_2$, and for all pairs of vertices $i$ and $j$ in $S_1$, $\operatorname{LCA}(i,j)$ is in $S_1$, where $\operatorname{LCA}(x,y)$ denotes the lowest common ancestor of vertices $x$ and $y$ on the tree. Note that a vertex set can have many different partial virtual trees.

Kawashiro Nitori wants to know for each possible $k$, if she performs the operation exactly $k$ times, in how many ways she can make $U={1}$ in the end? Two ways are considered different if there exists an integer $z$ ($1 \le z \le k$) such that after $z$ operations the sets $U$ are different.

Since the answer could be very large, you need to find it modulo $p$. It's guaranteed that $p$ is a prime number.

川崎二鳥是一位熱愛競賽編程的女孩。某天，她發現了一棵包含 $n$ 個頂點的有根樹，其中根節點為頂點 $1$。作為一名資深的題目構造者，她迅速想到了一個問題。

川崎二鳥擁有一個頂點集合 $U = \{1,2,\ldots,n\}$。她將在這棵樹與該集合上進行一場遊戲。每次操作中，她會選擇一個頂點集合 $T$，其中 $T$ 是 $U$ 的一個部分虛樹（partial virtual tree），並把 $U$ 更新為 $T$。

若頂點集合 $S_1$ 滿足以下條件，則稱其為頂點集合 $S_2$ 的一個部分虛樹：

• $S_1$ 是 $S_2$ 的子集；
• $S_1 \neq S_2$；
• 對於任意 $i,j \in S_1$，其最近公共祖先 $\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$ 是一個質數。

The first line contains two integers $n$ and $p$ ($2 \le n \le 2000$, $10^8 + 7 \le p \le 10^9+9$). It's guaranteed that $p$ is a prime number.

Each of the next $n-1$ lines contains two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$), representing an edge between $u_i$ and $v_i$.

It is guaranteed that the given edges form a tree.

第一行包含两个整数 $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$ 之间的一条边。

保证所给的边构成一棵树。

The only line contains $n-1$ integers — the answer modulo $p$ for $k=1,2,\ldots,n-1$.

唯一的一行包含 $n-1$ 个整数——即 $k=1,2,\ldots,n-1$ 时答案对 $p$ 取模的结果。

In the first test case, when $k=1$, the only possible way is:

1. ${1,2,3,4} \to {1}$.

When $k=2$, there are $6$ possible ways:

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}$.

When $k=3$, there are $6$ possible ways:

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}$.

在第一个测试用例中，当 $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}$。