PVHOI 2.0 - Bài 5 - Vẽ cây

View as PDF

Submit solution

Points: 0.70 (partial)
Time limit: 4.0s
Memory limit: 1G

Author:
Problem source:
PVHOI 2.0
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Rảnh rỗi vì không có ngiu, GS. PVH lấy giấy ra vẽ cây. GSPVH đã vẽ được một cây gồm ~n~ đỉnh và đánh số các đỉnh từ ~1~ đến ~n~.

Nhắc lại, cây là đồ thị vô hướng phi chu trình. Một cây gồm ~n~ đỉnh chắc chắn có ~n - 1~ cạnh.

Sau khi vẽ xong, GS. PVH chọn ra ~k~ đỉnh phân biệt trên cây và tô các đỉnh này bằng màu xanh lá cây. Tiếp theo đó, GS lại tiếp tục tô màu vàng vào những đỉnh mà GS coi là "xung yếu". Một đỉnh được GS coi là "xung yếu" khi và chỉ khi đỉnh này không được tô màu xanh lá cây; và nếu xóa đỉnh này ra khỏi cây, sẽ có hai đỉnh nào đó vừa được tô màu xanh lá cây không thể đi tới nhau nữa.

Tô màu đủ kiểu rồi, vẫn thấy mình còn dư quá nhiều thời gian, GS. PVH quyết định vẽ một bức tranh "siêu to khổng lồ to nhất Việt Nam" bằng việc liệt kê tất cả các cách chọn ra ~k~ đỉnh trong số ~n~ đỉnh của cây. Sau đó, với mỗi cách chọn, GS lại vẽ ra một cây và tô hai màu xanh lá cây và vàng vào các đỉnh theo quy tắc ở trên.

Thế nhưng, GS sắp hết bút sáp màu vàng. Vì vậy, GS. muốn nhờ bạn tính tổng số đỉnh được tô màu vàng trong bức tranh siêu to khổng lồ của mình.

Để làm khó bạn hơn, GS cho bạn trước một con số ~p~ và yêu cầu bạn phải tính ra kết quả theo modulo ~p~. Các bạn hãy chiều GS nhé.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~k~ và ~p~ ~(1 \leq k \leq n \leq 10^6, p \in \{10^9 + 19972207, 10^9 + 22071997\})~, lần lượt là số đỉnh trên cây, số đỉnh được GS. PVH lựa chọn để tô màu xanh lục và số ~p~ được nhắc đến trong đề bài.

Trong ~n - 1~ dòng còn lại, mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 \leq u, v \leq n)~ cho biết trên cây có một cạnh nối hai đỉnh ~u~ và ~v~.

Output

In ra tổng số đỉnh màu vàng trong bức tranh của GS. PVH.

Subtasks

Bộ test của bài được chia làm các subtask như sau:

  • Subtask ~1~ (~12~ test): ~n \leq 20~
  • Subtask ~2~ (~7~ test): ~n \leq 5000~
  • Subtask ~3~ (~2~ test): ~k = 1~
  • Subtask ~4~ (~6~ test): ~k = 2~
  • Subtask ~5~ (~10~ test): ~p = 10^9 + 19972207~
  • Subtask ~6~ (~16~ test): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~70~ điểm.

Ví dụ

Input

6 3 1019972207
1 2
2 3
3 4
3 5
3 6

Output

16

Giải thích

Dưới đây là bức tranh siêu to khổng lồ to nhất Việt Nam do GS. PVH vẽ trong ví dụ ở trên. Có tất cả ~20~ cách chọn ra ~k = 3~ đỉnh trong một cây gồm ~n = 6~ đỉnh. Tổng số đỉnh được tô màu vàng trong các cách này là.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.