## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ vertices. The root is vertex $1$. As an advanced problem setter, she quickly thought of a problem.

Kawashiro Nitori has a vertex set $U=\left\{1,2,\dots ,n\right\}$. 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}\ne {S}_{2}$, and for all pairs of vertices $i$ and $j$ in ${S}_{1}$$\mathrm{LCA}\left(i,j\right)$ is in ${S}_{1}$, where $\mathrm{LCA}\left(x,y\right)$ 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

Solution Click Below:-  👉
👇👇👇👇👇

many ways she can make $U=\left\{1\right\}$ 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

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.

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$ lines contains two integers ${u}_{i}$${v}_{i}$ ($1\le {u}_{i},{v}_{i}\le 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,\dots ,n-1$.