Phân rã trọng tâm (Centroid Decomposition) đếm cặp đường đi độ dài <= K
Cho một cây gồm N đỉnh (1 ≤ N ≤ 105) và số nguyên K (1 ≤ K ≤ N). Khoảng cách giữa hai đỉnh u và v là số lượng cạnh trên đường đi đơn giữa chúng.
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: tree representation, dfs, binary search.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu định nghĩa Trọng tâm của cây (Tree Centroid): Nút mà nếu xóa đi thì mỗi thành phần liên thông còn lại có kích thước không quá N/2.
- Cài đặt chia để trị trên cây bằng Centroid Decomposition với độ sâu đệ quy tối đa O(log N).
- Đếm số cặp nút có khoảng cách đường đi ≤ K trong thời gian O(N log2 N).
Mô tả bài toán
Cho một cây gồm N đỉnh (1 ≤ N ≤ 105) và số nguyên K (1 ≤ K ≤ N). Khoảng cách giữa hai đỉnh u và v là số lượng cạnh trên đường đi đơn giữa chúng.
Hãy đếm số cặp đỉnh không thứ tự (u, v) (1 ≤ u < v ≤ N) sao cho khoảng cách giữa u và v không vượt quá K.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
- Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
- Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 2 số nguyên N và K (1 ≤ N ≤ 105, 1 ≤ K ≤ N).
- N-1 dòng tiếp theo: Mỗi dòng gồm 2 số nguyên u, v (1 ≤ u, v ≤ N) mô tả một cạnh của cây.
Output
- In ra một số nguyên duy nhất là số lượng cặp đỉnh thỏa mãn.
Ràng buộc
- 1 ≤ N ≤ 105.
- 1 ≤ K ≤ N.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
5 2
1 2
1 3
2 4
2 5
Output
8
*Giải thích:* Các cặp có khoảng cách ≤ 2 gồm:
Khoảng cách 1: (1,2), (1,3), (2,4), (2,5) (4 cặp).
Khoảng cách 2: (1,4), (1,5), (2,3), (4,5) (4 cặp).
Tổng cộng: 4 + 4 = 8 cặp.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
