Đường kính

Mã bài: olpicpc053c12d Nhóm: Uncategorized Dạng bài: Undefined

Giới hạn thời gian: 1,0 s
Giới hạn bộ nhớ: 256 MB
Điểm: 2.500một phần
Tỉ lệ AC: 19,0%
Người giải: 7

Cho đồ thị dạng cây gồm $n$ ~n~ đỉnh được đánh số từ $1$ ~1~ đến $n$ ~n~. Khoảng cách giữa hai đỉnh của cây được định nghĩa là số cạnh nằm trên đường đi nối hai đỉnh đó.

Gọi $d$ ~d~ là đường kính của cây $($ ~(~khoảng cách lớn nhất trong số các cặp đỉnh $)$ ~)~. Đếm số cách chọn tập hợp ít nhất $2$ ~2~ đỉnh sao cho khoảng cách giữa hai đỉnh bất kỳ trong tập hợp bằng chính xác $d$ ~d~.

Input

Dòng đầu tiên chứa số nguyên $n$ ~n~ $(2 \le n \le 2 \times 10^5)$ ~(2 \le n \le 2 \times 10^5)~.
$n-1$ ~n-1~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa hai số nguyên $u_i$ ~u_i~ và $v_i$ ~v_i~ mô tả cạnh thứ $i$ ~i~ nối hai đỉnh $u_i-v_i$ ~u_i-v_i~ $(1 \le u_i,v_i \le n$ ~(1 \le u_i,v_i \le n~ ; $u \neq v)$ ~u \neq v)~.
Dữ liệu đảm bảo đồ thị đã cho là một cây hợp lệ.

Output

In ra số cách chọn tập hợp các đỉnh, kết quả chia lấy dư cho $998244353$ ~998244353~.

Examples

Sample Input

Sample Output

Scoring

Subtask $1$ ~1~ $-$ ~-~ $750$ ~750~ điểm : $n \le 10$ ~n \le 10~
Subtask $2$ ~2~ $-$ ~-~ $750$ ~750~ điểm : $n \le 500$ ~n \le 500~
Subtask $3$ ~3~ $-$ ~-~ $1000$ ~1000~ điểm : Không có ràng buộc gì thêm

Notes

Trong ví dụ, với $d=3$ ~d=3~, ta có thể chọn tập hợp các đỉnh: $\{3,5\}$ ~\{3,5\}~ hoặc $\{4,5\}$ ~\{4,5\}~.

Bình luận

GA
gaming10054 Newbie 09/09/2024 12:50

Tại sao đề kêu mod 1e9+7 thì wa mà mod 998244353 thì lại ac thế anh ra đề gì đó ơi

Điểm bình chọn: 0
- Yunan Master 11/09/2024 18:10
  
  Sorry bạn !!! Mình đã sửa lại đề bài nhé
  
  Điểm bình chọn: 1

Bạn cần đăng nhập để viết bình luận, trả lời và bình chọn.

Đăng nhập để bình luận