Olympic chuyên KHTN 2024 - Classic Tree
Xem dạng PDF
Gửi bài giải
Điểm:
45,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho cây có ~n~ đỉnh gốc ở ~1~. Mỗi đỉnh của cây có thể được tô bằng một trắng hoặc đen. Một cách tô được gọi là hợp lệ nếu như mỗi subtree có hiệu giữa số đỉnh trắng và đen là bé hơn hoặc bằng ~1~. Đếm có bao nhiêu cách tô hợp lệ ~mod\ 998244353~.
Input
Dòng đầu tiên gồm ~n~ là số đỉnh của cây ~(1 \le n \le 5 \cdot 10^5)~
~n-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số ~u, v~ thể hiện có ~1~ cạnh nối giữa ~2~ đỉnh đấy.
Output
Một số trên một dòng là kết quả của bài toán ~mod\ 998244353~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n \le 20~ |
| 2 | ~20\%~ | ~n \le 10^3~ |
| 3 | ~20\%~ | ~n \le 10^5~ |
| 4 | ~20\%~ | ~n \le 3 \cdot 10^5~ |
| 5 | ~20\%~ | ~n \le 5 \cdot 10^5~ |
Sample Input 1
5
1 2
3 4
1 4
1 5
Sample Output 1
12
Bình luận