[Solution] Partial Virtual Trees Codeforces Solution

F. Partial Virtual Trees

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

A vertex set S1$S_1$ is a partial virtual tree of a vertex set S2$S_2$, if S1$S_1$ is a subset of S2$S_2$, S1≠S2$S_1\ne S_2$, and for all pairs of vertices i$i$ and j$j$ in S1$S_1$, LCA(i,j)$\mathrm{LCA}(i,j)$ is in S1$S_1$, where LCA(x,y)$\mathrm{LCA}(x,y)$ denotes the lowest common ancestor of vertices x$x$ and y$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$k$, if she performs the operation exactly k$k$ times, in how

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 many ways she can make U={1}$U=\{1\}$ in the end? Two ways are considered different if there exists an integer z$z$ (1≤z≤k$1\le z\le k$) such that after z$z$ operations the sets U$U$ are different.

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

Input

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

Difference Operations Codeforces Solution

Difference of GCDs Codeforces Solution

Doremy's IQ Codeforces Solution

Difference Array Solution Codeforces 

Partial Virtual Trees Codeforces Solution

DFS Trees Codeforces Solution

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

It is guaranteed that the given edges form a tree.

Output

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