Lời giải mặc định độc giả đã biết và học về cầu (bridge) và Bridge Tree.

Ta sẽ dựng Bridge Tree của đồ thị. Vậy ta sẽ xem truy vấn trên Bridge Tree hoạt động thế nào.

Gọi:

• ~LCA(u, v):~ Cha chung thấp nhất của ~u~ và ~v~.
• ~d(u, v):~ Số cạnh trên đường đi ~u \rightarrow v~.
• ~inter(a, b, c, d):~ Số cạnh chung của hai đường đi ~a \rightarrow b~ và ~c \rightarrow d~.

Gọi ~A', B', C', D'~ lần lượt là các nút nằm trên Bridge Tree đại diện cho ~A, B, C, D~. Vậy khi thêm một cạnh nối ~A - B~, đồng nghĩa với việc xóa hết tất cả các cạnh từ ~A' \rightarrow B'~ trên Bridge Tree và đáp án lúc này ~d(C', D')~.

Như vậy, đáp án cho một truy vấn sẽ là: ~d(C', D') - inter(A', B', C', D')~ trên Bridge Tree ban đầu.

Truy vấn ~d(C', D')~ có thể giải quyết bằng ~LCA~ cơ bản, nên ta sẽ tìm cách trả lời truy vấn tìm số cạnh chung.

Gọi ~u = LCA(A', B'), v = LCA(C', D')~.

Ta có: ~inter(A', B', C', D') = inter(u, A', v, C') + inter(u, A', v, D') + inter(u, B', v, C') + inter(u, B', v, D')~.

Lúc này các đường đi cần xét là các đường thẳng từ ~LCA~ đi xuống, nên ta có thể dễ dàng tính ~inter()~ bằng cách chia một vài trường hợp.

Độ phức tạp: ~O(n \log{n})~.

Code mẫu: https://ideone.com/E0515h