Partial Virtual Trees
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
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.
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.
The only line contains $n-1$ integers — the answer modulo $p$ for $k=1,2,\ldots,n-1$.
Input
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
The only line contains $n-1$ integers — the answer modulo $p$ for $k=1,2,\ldots,n-1$.
4 998244353
1 2
2 3
1 4
7 100000007
1 2
1 3
2 4
2 5
3 6
3 7
8 1000000007
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 6 6
1 47 340 854 880 320
1 126 1806 8400 16800 15120 5040
Note
In the first test case, when $k=1$, the only possible way is:
- $\{1,2,3,4\} \to \{1\}$.
When $k=2$, there are $6$ possible ways:
- $\{1,2,3,4\} \to \{1,2\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,4\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3,4\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,4\} \to \{1\}$.
When $k=3$, there are $6$ possible ways:
- $\{1,2,3,4\} \to \{1,2,3\} \to \{1,2\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,3\} \to \{1,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,4\} \to \{1,2\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,4\} \to \{1,4\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3,4\} \to \{1,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3,4\} \to \{1,4\} \to \{1\}$.
20240116杂题选讲
- Status
- Done
- Rule
- IOI
- Problem
- 6
- Start at
- 2024-1-16 18:00
- End at
- 2024-1-18 18:00
- Duration
- 48 hour(s)
- Host
- Partic.
- 25