Partial Virtual Trees
Contest: Codeforces Round 808 (Div. 1)
Difficulty rating: 3000
Tags: combinatorics, dfs and similar, dp, math, 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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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\}$$$.

Example input:
4 998244353
1 2
2 3
1 4

Example output:
1 6 6

Example input:
7 100000007
1 2
1 3
2 4
2 5
3 6
3 7

Example output:
1 47 340 854 880 320

Editorial:
First ignore the requirement that the virtual tree cannot be the entire tree. Then we count the number of ways without this requirement for all $$$k$$$ using DP.
$$$dp_{x,i}$$$ is the number of ways to delete everything in the subtree of $$$x$$$ in exact $$$i$$$ operations. Node $$$x$$$ must be deleted at some time $$$j \le i$$$ and all but at most one child subtree of $$$x$$$ must be deleted before time $$$j$$$.
Let:
• $$$C_x$$$ be the set of $$$x$$$'s children.
• $$$S_{x,i}=\sum_{j\le i} dp_{x,i}$$$
• $$$D_{x,j}=\prod_{u\in C(x)}S_{u,j}$$$
Then
$$$$$$ \begin{aligned} dp_{x,i} &=\sum_{j < i}\sum_{u\in C_x}\dfrac{dp_{u,i}D_{x,j}}{S_{u,j}} + \prod_{u\in C_x} S_{u,i}\\ &=\sum_{u \in C_x}dp_{u,i} \sum_{j < i} \dfrac{D_{x,j}}{S_{u,j}}+\prod_{u \in C_x}S_{u,i} \end{aligned} $$$$$$
Specially, when $$$x$$$ is root ($$$x=1$$$), $$$x$$$ is the last one to be deleted. So $$$dp_{x,i}=\prod_{u\in C_x} S_{u,i}$$$ in this case.
It's not hard to computer this with prefix sums in $$$O(n^2)$$$ time.
Then consider the requirement that the virtual tree cannot be the entire tree. Let the real answer be $$$Ans_k$$$. Then
$$$$$$ \begin{aligned} dp_{1,i} &= \sum_{j=0}^{i} \binom{i}{j}Ans_j \\ Ans_i &= dp_{1,i} - \sum_{j=0}^{i-1} \binom{i}{j} Ans_j \end{aligned} $$$$$$
So we can figure out the real answer in $$$O(n^2)$$$ time.