Nhận thấy ~pi < i~, do đó đường đi từ ~i~ về ~1~ sẽ đi qua các đỉnh theo thứ tự giảm dần. Thêm nữa, khi thay đổi cạnh ~(i, pi)~, thì đường đi có dạng sau sẽ thay đổi: ~v1 \rightarrow v2 \rightarrow \dots \rightarrow vk~ với sao cho tồn tại ~j < k~ thỏa ~vj = i, v_{j+1} = pi~ và ~vk = 1~.

Ta sẽ thử chia đường đi này thành các đoạn:

• ~v1 \rightarrow v2 \rightarrow \dots \rightarrow v_{x_1}~
• ~v_{x1} \rightarrow v{x_1+1}~
• ~v_{x1+1} \rightarrow v{x1+2} \rightarrow \dots \rightarrow v{x_2}~
• ~\dots~
• ~v_{xk} \rightarrow v{x_k+1} \rightarrow \dots \rightarrow 1~.

Khi thay đổi một cạnh ~(i, pi)~, chính là đang thay đổi đường đi của một cạnh ~(vj, v_{j+1})~, nhận thấy rằng cạnh ~vj \rightarrow v{j+1}~ chỉ làm ảnh hưởng đến đúng một chuỗi đường đi chứa cạnh này.

Do đó, ta sử dụng kĩ thuật chia căn cho bài toán này, chia mảng thành các block độ dài ~\sqrt{N}~. Gọi ~fi~ là những người bị nghi ngờ khi từ ~i~ "nhảy ra" khỏi block chứa ~i~, và ~Pi~ là vị trí sau khi "nhảy ra".

• Truy vấn ~1~: Ta chỉ thay đổi đúng một chuỗi đường đi độ dài tối đa ~\sqrt{N}~ trong block chứa ~u~. Độ phức tạp: ~O(\sqrt{N})~.
• Truy vấn ~2~: Ta nhảy từ ~u~ sang ~Pu~, đến khi gặp block đầu tiên, ta sẽ nhảy từ ~u~ sang ~pu~. Độ phức tạp: ~O(\sqrt{N})~.
  • Mỗi lần từ ~u \rightarrow Pu~ ta sẽ giảm một block, do đó là chỉ nhảy tối đa ~\sqrt{N}~ lần (vì chỉ có ~\sqrt{N}~ block)
  • Mỗi lần từ ~u \rightarrow pu~ ta chỉ nhảy tối đa ~\sqrt{N}~ lần (do chuỗi đường đi chỉ dài tối đa ~\sqrt{N}~).

Độ phức tạp: ~O(Q\sqrt{N})~.