Đếm đường đi
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một cây ~N~ đỉnh, hãy đếm số lượng đường đi phân biệt có độ dài trong khoàng ~[k_1,k_2]~.
Input
Dòng đầu gồm ~3~ số ~N,k_1,k_2~ ~(1\le k_1\le k_2\le N\le 2*10^5)~
~N-1~ dòng tiếp theo, mỗi dòng gồm hai số thể hiện cạnh trên cây.
Output
- Gồm ~1~ số là số lượng đường đi phân biệt
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| ~1~ | ~30\%~ | ~N\le5000~ |
| ~2~ | ~20\%~ | ~k_1=k_2~ |
| ~3~ | ~50\%~ | Không có ràng buộc gì thêm |
Sample Input 1
5 2 3
1 2
2 3
3 4
3 5
Sample Output 1
6
Bình luận
Lưu ý về đề bài: độ dài đường đi từ u tới v là số lượng cạnh trên đường đi từ u tới v.
Với test ví dụ, ta có các đường đi thỏa mãn là: