Partial Virtual Trees Solution Codeforces

Table of Contents

Partial Virtual Trees Solution Codeforces

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

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

A vertex set S1S1 is a partial virtual tree of a vertex set S2S2, if S1S1 is a subset of S2S2S1S2S1≠S2, and for all pairs of vertices ii and jj in S1S1LCA(i,j)LCA⁡(i,j) is in S1S1, where LCA(x,y)LCA⁡(x,y) denotes the lowest common ancestor of vertices xx and yy on the tree. Note that a vertex set can have many different partial virtual trees.

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

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

Input Partial Virtual Trees Solution Codeforces

The first line contains two integers nn and pp (2n20002≤n≤2000108+7p109+9108+7≤p≤109+9). It’s guaranteed that pp is a prime number.

Each of the next n1n−1 lines contains two integers uiuivivi (1ui,vin1≤ui,vi≤n), representing an edge between uiui and vivi.

It is guaranteed that the given edges form a tree.

Output Partial Virtual Trees Solution Codeforces

The only line contains n1n−1 integers — the answer modulo pp for k=1,2,,n1k=1,2,…,n−1.

Examples
input

Copy
4 998244353
1 2
2 3
1 4
output

Copy
1 6 6
input

Copy
7 100000007
1 2
1 3
2 4
2 5
3 6
3 7
output

Copy
1 47 340 854 880 320
input

Copy
8 1000000007
1 2
2 3
3 4
4 5
5 6
6 7
7 8
output

Copy
1 126 1806 8400 16800 15120 5040

Note Partial Virtual Trees Solution Codeforces

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

  1. {1,2,3,4}{1}{1,2,3,4}→{1}.

When k=2k=2, there are 66 possible ways:

  1. {1,2,3,4}{1,2}{1}{1,2,3,4}→{1,2}→{1};
  2. {1,2,3,4}{1,2,3}{1}{1,2,3,4}→{1,2,3}→{1};
  3. {1,2,3,4}{1,2,4}{1}{1,2,3,4}→{1,2,4}→{1};
  4. {1,2,3,4}{1,3}{1}{1,2,3,4}→{1,3}→{1};
  5. {1,2,3,4}{1,3,4}{1}{1,2,3,4}→{1,3,4}→{1};
  6. {1,2,3,4}{1,4}{1}{1,2,3,4}→{1,4}→{1}.

When k=3k=3, there are 66 possible ways:

  1. {1,2,3,4}{1,2,3}{1,2}{1}{1,2,3,4}→{1,2,3}→{1,2}→{1};
  2. {1,2,3,4}{1,2,3}{1,3}{1}{1,2,3,4}→{1,2,3}→{1,3}→{1};
  3. {1,2,3,4}{1,2,4}{1,2}{1}{1,2,3,4}→{1,2,4}→{1,2}→{1};
  4. {1,2,3,4}{1,2,4}{1,4}{1}{1,2,3,4}→{1,2,4}→{1,4}→{1};
  5. {1,2,3,4}{1,3,4}{1,3}{1}{1,2,3,4}→{1,3,4}→{1,3}→{1};
  6. {1,2,3,4}{1,3,4}{1,4}{1}{1,2,3,4}→{1,3,4}→{1,4}→{1}.

 

For Solution

Click Here

Leave a Comment