trang chủ / đề bài / running / lời giải

Cú Bay Đêm

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
Tác giả: huunguyenhuunguyen

Lời giải: Cú Bay Đêm

Hướng tiếp cận

Với mỗi con cú bay từ s đến t 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 v có bao nhiêu con cú đi qua v đúng thời điểm w[v].

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 O(NM) quá chậm.

Nhận xét quan trọng

Tách đường đi s→t thành hai phần qua L=LCA(s,t):

Phần đi lên (s→L): Con cú ở đỉnh v tại thời điểm depth[s]−depth[v].

Học sinh tại v thấy cú khi w[v]=depth[s]−depth[v], tức depth[s]=depth[v]+w[v].

Phần đi xuống (L→t): Con cú ở đỉnh v tại thời điểm depth[s]−2·depth[L]+depth[v].

Học sinh tại v thấy cú khi depth[s]−2·depth[L]=w[v]−depth[v].

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:

  1. Tính LCA bằng binary lifting trong O(logN) cho mỗi truy vấn.

  2. Tạo sự kiện tại các đỉnh:

    • Phần đi lên: thêm +1 vào bucket tại đỉnh s với khóa depth[s], thêm −1 tại parent(L).
    • Phần đi xuống: thêm +1 tại đỉnh t với khóa depth[s]−2·depth[L], thêm −1 tại L (không phải parent(L), để tránh đếm trùng tại LCA).
  3. DFS trên cây: Tại mỗi đỉnh v:

    • 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 v.
    • Đáp án tại v = giá trị bucket sau - giá trị bucket trước.

Ý tưởng cốt lõi: Khi DFS xong cây con gốc v và áp dụng sự kiện tại v, bucket chứa đúng các con cú có điểm đầu/cuối nằm trong cây con gốc v. Hiệu (sau - trước) đếm đúng số cú liên quan đến cây con v.

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 L thay vì parent(L).

Độ phức tạp

  • Thời gian: O((N+M)logN) — LCA cho M truy vấn, DFS O(N+M).
  • Bộ nhớ: O(N+M).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0