Cây Đũa Phép Cơm Nguội

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

1. 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.
2. 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).
3. 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

1. 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.

2. 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).

3. link(x, y): Nối hai cây - make_root($x$), đặt cha của $x$ là $y$.

4. cut(x, y): Tách cạnh $x$-$y$ - make_root($x$), access($y$), ngắt liên kết.

5. 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$).

6. 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.