Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải: Cú Bay Đêm
Hướng tiếp cận
Với mỗi con cú bay từ đến trên cây, đường đi qua LCA (tổ tiên chung gần nhất). Ta cần đếm tại mỗi đỉnh có bao nhiêu con cú đi qua đúng thời điểm .
Bài toán yêu cầu xử lý hiệu quả — brute force duyệt từng đường đi sẽ có độ phức tạp quá chậm.
Nhận xét quan trọng
Tách đường đi thành hai phần qua :
Phần đi lên (): Con cú ở đỉnh tại thời điểm .
Học sinh tại thấy cú khi , tức .
Phần đi xuống (): Con cú ở đỉnh tại thời điểm .
Học sinh tại thấy cú khi .
Thuật toán
Sử dụng kỹ thuật đếm trên cây với mảng hiệu (difference on tree) kết hợp bucket counting:
Tính LCA bằng binary lifting trong cho mỗi truy vấn.
Tạo sự kiện tại các đỉnh:
- Phần đi lên: thêm vào bucket tại đỉnh với khóa , thêm tại .
- Phần đi xuống: thêm tại đỉnh với khóa , thêm tại (không phải , để tránh đếm trùng tại LCA).
DFS trên cây: Tại mỗi đỉnh :
- Ghi nhận giá trị bucket trước khi xử lý cây con.
- Xử lý tất cả các cây con.
- Áp dụng các sự kiện tại .
- Đáp án tại = giá trị bucket sau - giá trị bucket trước.
Ý tưởng cốt lõi: Khi DFS xong cây con gốc và áp dụng sự kiện tại , bucket chứa đúng các con cú có điểm đầu/cuối nằm trong cây con gốc . Hiệu (sau - trước) đếm đúng số cú liên quan đến cây con .
Tránh đếm trùng tại LCA bằng cách xóa sự kiện phần đi xuống ngay tại thay vì .
Độ phức tạp
- Thời gian: — LCA cho truy vấn, DFS .
- Bộ nhớ: .
https://oj.chuyentin.pro/problem/running/editorial
Bình luận