Cây & Đồ thị
Centroid Decomposition
ID: #105
Xem trên trang chủ
Thời gian (Time)
O(N log N)
Không gian (Space)
O(N)
Mô tả nguyên lý
Phân rã trọng tâm cây để giải quyết các bài toán đếm đường đi khoảng cách hoặc cây phân cấp.
Cài đặt mẫu (Implementation)
// Tìm tâm trọng tâm (centroid) của cây, chia nhỏ cây thành các bài toán con độc lập qua đệ quy.
Cây & Đồ thị
Heavy-Light Decomposition (HLD)
ID: #104
Xem trên trang chủ
Thời gian (Time)
O(log^2 N) mỗi truy vấn
Không gian (Space)
O(N)
Mô tả nguyên lý
Phân rã cây thành các đường đi nặng/nhẹ để thực hiện truy vấn trên cây cực nhanh bằng Segment Tree.
Cài đặt mẫu (Implementation)
// Chia các cây con thành các chuỗi đường đi nặng để tối ưu hóa việc cập nhật và truy vấn đường đi trên cây.