planets_queries2

Đồ thị hàm: mỗi đỉnh có đúng một cạnh đi ra. Đỉnh $1$ dịch chuyển đến $2$, đỉnh $2$ đến $3$, đỉnh $3$ đến $1$ (chu trình độ dài $3$). Tương tự, $4 \to 5 \to 6 \to 4$ tạo thành chu trình thứ hai. Mỗi thành phần liên thông yếu có dạng chữ rho – ở đây cả hai đều là chu trình thuần túy.

Thành phần $1$: chu trình $1 \to 2 \to 3 \to 1$ có độ dài $3$. Cả ba đỉnh đều nằm trên chu trình (độ sâu $0$).

Thành phần $2$: chu trình $4 \to 5 \to 6 \to 4$ có độ dài $3$. Cũng là chu trình thuần túy. Các đỉnh ở khác thành phần không bao giờ có thể đến được nhau.

Bây giờ ta xây dựng bảng nhảy đôi (binary lifting). $lift[k][i]$ = đỉnh đến được từ $i$ sau $2^k$ lần dịch chuyển. Hàng $0$ là $k=0$ ($1$ bước), hàng $1$ là $k=1$ ($2$ bước), hàng $2$ là $k=2$ ($4$ bước).

Hàng $k=0$: $lift[0][i] = t[i]$, đích dịch chuyển trực tiếp. Đỉnh $1 \to 2$, $2 \to 3$, $3 \to 1$, $4 \to 5$, $5 \to 6$, $6 \to 4$. Đây chính là danh sách cạnh ban đầu.

Hàng $k=1$: $lift[1][i] = lift[0][lift[0][i]]$, đỉnh đến được sau $2$ bước. Với đỉnh $1$: $lift[0][lift[0][1]] = lift[0][2] = 3$. Mỗi ô được tính bằng cách nối hai bước nhảy đơn.

Hàng $k=2$: $lift[2][i] = lift[1][lift[1][i]]$, đỉnh đến được sau $4$ bước. Vì chu trình có độ dài $3$, nhảy $4$ bước tương đương nhảy $1$ bước. Đỉnh $1$ sau $4$ bước: $1 \to 2 \to 3 \to 1 \to 2$, nên $lift[2][1]=2$. Nhận thấy nó trùng với $lift[0][1]$ – vì $4 \bmod 3 = 1$ bước.

Bảng binary lifting đã hoàn thành. Giờ ta có thể nhảy bất kỳ đỉnh nào về phía trước một khoảng cách $d$ trong $O(\log d)$ bằng cách phân tích $d$ thành tổng các lũy thừa của $2$. Bây giờ hãy trả lời các truy vấn.

Truy vấn $1$: khoảng cách từ đỉnh $1$ đến đỉnh $3$? Cả hai đều thuộc thành phần $1$ (cùng chu trình). Ta cần đi theo các cạnh từ $1$ và đếm số bước cho đến khi gặp $3$.

Bước $1$: dịch chuyển từ $1$ đến $2$. Chưa đến $3$. Tiếp tục.

Bước $2$: dịch chuyển từ $2$ đến $3$. Đã đến đích! Khoảng cách $= 2$. Trên chu trình độ dài $3$, khoảng cách thuận từ vị trí $0$ đến vị trí $2$ là $(2 - 0) \bmod 3 = 2$.

Đáp án truy vấn $(1, 3) = 2$. Hai lần dịch chuyển: $1 \to 2 \to 3$.

Truy vấn $2$: khoảng cách từ đỉnh $4$ đến đỉnh $2$? Đỉnh $4$ thuộc thành phần $2$, đỉnh $2$ thuộc thành phần $1$. Chúng có cùng thành phần không?

Khác thành phần! Đỉnh $4$ thuộc chu trình $\{4,5,6\}$ còn đỉnh $2$ thuộc chu trình $\{1,2,3\}$. Không có chuỗi dịch chuyển nào có thể đi giữa hai thành phần. Trả về $-1$ ngay lập tức.

Đáp án truy vấn $(4, 2) = -1$. Không thể đến được – hai thành phần liên thông khác nhau trong đồ thị hàm.

Truy vấn bổ sung: khoảng cách từ đỉnh $1$ đến đỉnh $1$? Cùng nguồn và đích.

Đáp án $= 0$. Không cần dịch chuyển – bạn đã ở đó rồi. Lưu ý: khoảng cách vòng sẽ là $3$ (đi hết một vòng), nhưng giá trị nhỏ nhất là $0$ vì $a = b$.

Để xử lý các đỉnh đuôi (cây treo vào chu trình), ta cần thêm thông tin về độ sâu. Nếu $b$ nằm trên đường đi từ $a$ đến chu trình, ta nhảy $a$ về phía trước $(depth[a] - depth[b])$ bước rồi kiểm tra có đến đúng $b$ không. Nếu $b$ nằm trên chu trình, ta đưa $a$ đến chu trình rồi tính khoảng cách vòng.

Tổng kết: trong đồ thị hàm, binary lifting giúp ta nhảy về phía trước hiệu quả, phát hiện chu trình xác định các thành phần, và kết hợp cả hai cho ta $O(\log n)$ mỗi truy vấn. Tổng độ phức tạp: $O((n + q) \log n)$. Ý tưởng cốt lõi là khả năng tiếp cận trong đồ thị hàm chỉ đi theo chiều thuận trên đường đi duy nhất từ mỗi đỉnh vào chu trình của nó.