Nhận thấy ~p_i < 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, p_i)~, thì đường đi có dạng sau sẽ thay đổi: ~v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_k~ với sao cho tồn tại ~j < k~ thỏa ~v_j = i, v_{j+1} = p_i~ và ~v_k = 1~.

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

• ~v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_{x_1}~
• ~v_{x_1} \rightarrow v_{x_1+1}~
• ~v_{x_1+1} \rightarrow v_{x_1+2} \rightarrow \dots \rightarrow v_{x_2}~
• ~\dots~
• ~v_{x_k} \rightarrow v_{x_k+1} \rightarrow \dots \rightarrow 1~.

Khi thay đổi một cạnh ~(i, p_i)~, chính là đang thay đổi đường đi của một cạnh ~(v_j, v_{j+1})~, nhận thấy rằng cạnh ~v_j \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 ~f_i~ là những người bị nghi ngờ khi từ ~i~ "nhảy ra" khỏi block chứa ~i~, và ~P_i~ 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 ~P_u~, đến khi gặp block đầu tiên, ta sẽ nhảy từ ~u~ sang ~p_u~. Độ phức tạp: ~O(\sqrt{N})~.
  • Mỗi lần từ ~u \rightarrow P_u~ 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 p_u~ 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})~.