Atcoder Educational DP Contest V - Subtree

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cây là đồ thị vô hướng, liên thông và không có chu trình. Một cây ~N~ đỉnh sẽ có ~(N - 1)~ cạnh. Cho một cây có ~N~ đỉnh, các đỉnh được đánh số ~1, 2, ..., N~. Cạnh thứ ~i~ ~(1 \le i \le (N - 1))~ kết nối 2 đỉnh ~x_{i}~ và ~y_{i}~.

Taro quyết định tô mỗi đỉnh của cây bởi một trong hai màu trắng hoặc đen, sao cho với hai đỉnh được tô đen bất kì, tất cả các đỉnh trên đường đi giữa hai đỉnh đó cũng được tô đen.

Bạn được cho một số nguyên dương ~M~. Với mỗi ~v~ ~(1 \le v \le N)~, hãy trả lời câu hỏi dưới đây:

Giả sử đỉnh ~v~ đã được tô màu đen, có bao nhiêu cách tô ~(n - 1)~ đỉnh còn lại để thỏa mãn điều kiện trên? Do đáp án có thể rất lớn, in ra kết quả modulo ~M~.

Input

Dòng đầu tiên chứa 2 số ~N~ và ~M~ - số đỉnh và modulo.

Dòng thứ ~i~ trong ~(N - 1)~ dòng tiếp theo chứa ~2~ số ~x_{i}~ và ~y_{i}~ - ~2~ đỉnh được nối bởi cạnh thứ ~i~.

Output

In ra ~N~ dòng, dòng thứ ~i~ in ra đáp án cho câu hỏi trên với đỉnh ~i~ theo modulo ~M~.

Giới hạn

  • Tất cả các giá trị trong input là số nguyên.
  • ~1 \le N \le 10^5~
  • ~2 \le M \le 10^9~ (lưu ý rằng ~M~ không nhất thiết phải là số nguyên tố)
  • ~1 \le x_{i}, y_{i} \le N~ ~(1 \le i \le (N - 1))~
  • Đồ thị đã cho là cây.

Sample Input 1

3 100
1 2
2 3

Sample Output 1

3
4
3

Sample Input 2

4 100
1 2
1 3
1 4

Sample Output 2

8
5
5
5

Sample Input 3

1 100

Sample Output 3

1

Sample Input 4

10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

Sample Output 4

0
0
1
1
1
0
1
0
1
1

Giải thích test đề thứ nhất

Trên đây là tất cả những cách tô màu thỏa mãn điều kiện đề bài. (Cách tô đỉnh ~1~ và ~3~ đen không thỏa mãn do đồ thị tạo bởi ~2~ đỉnh ~1~ và ~3~ không liên thông)

Trong ~7~ cách trên, có

  • ~3~ cách có đỉnh ~1~ được tô màu đen
  • ~4~ cách có đỉnh ~2~ được tô màu đen
  • ~3~ cách có đỉnh ~3~ được tô màu đen

Comments

Please read the guidelines before commenting.


There are no comments at the moment.