Hướng dẫn giải của Cây Đũa Phép Cơm Nguội

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ả: huunguyen

Hướng tiếp cận

Bài toán yêu cầu xử lý các thao tác trên rừng động (dynamic forest): nối hai cây, tách một cây, truy vấn tổng trên đường đi, và cập nhật giá trị tại một đỉnh. Đây là bài toán kinh điển của Link-Cut Tree (LCT).

Nhận xét quan trọng

Các thao tác link/cut thay đổi cấu trúc cây liên tục, nên không thể dùng Heavy-Light Decomposition (HLD) hay Euler Tour Tree trên cây tĩnh.
Link-Cut Tree cho phép thực hiện tất cả 4 thao tác trong thời gian $O (\log N)$ khấu hao (amortized).
Tổng trên đường đi có thể lên đến $10^{5} \times 10^{9} = 10^{14}$ , cần dùng long long.

Thuật toán

Link-Cut Tree (LCT)

LCT biểu diễn rừng bằng tập các Splay Tree (cây nhị phân tự cân bằng). Mỗi đỉnh lưu:

val[x]: giá trị (sức mạnh) tại đỉnh $x$
sum[x]: tổng giá trị trong Splay subtree gốc tại $x$
ch[x][0/1]: con trái/phải trong Splay Tree
fa[x]: cha trong Splay Tree (hoặc path-parent)
rev[x]: cờ đảo ngược (lazy propagation cho make_root)

Các thao tác chính

access(x): Đưa đỉnh $x$ lên gốc của Splay Tree chứa toàn bộ đường đi từ $x$ đến gốc cây biểu diễn. Sau đó splay $x$ lên gốc.
make_root(x): Làm $x$ thành gốc cây biểu diễn bằng cách access( $x$ ) rồi đảo ngược đường preferred path (dùng lazy reverse flag).
link(x, y): Nối hai cây - make_root( $x$ ), đặt cha của $x$ là $y$ .
cut(x, y): Tách cạnh $x$ - $y$ - make_root( $x$ ), access( $y$ ), ngắt liên kết.
query(x, y): Tổng đường đi - make_root( $x$ ), access( $y$ ), trả về sum[ $y$ ] (lúc này Splay Tree gốc $y$ chứa đúng đường đi $x \to y$ ).
update(x, v): Splay( $x$ ) lên gốc, cập nhật val[ $x$ ] = $v$ , push_up.

Splay Tree

Mỗi Splay Tree lưu trữ một preferred path trong cây biểu diễn. Thao tác splay dùng zig-zig/zig-zag rotation để đưa đỉnh lên gốc, với điều kiện dừng khi đỉnh không còn là con (trái/phải) của cha nó trong Splay Tree (tức là đỉnh đã ở gốc của Splay Tree riêng, chỉ còn path-parent pointer).

Độ phức tạp

Thời gian: $O ((N + Q) \log N)$ khấu hao. Mỗi thao tác access/splay tốn $O (\log N)$ amortized.
Bộ nhớ: $O (N)$ - mỗi đỉnh lưu hằng số biến.

Bình luận

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