Tutorial — Kênh truyền

Thời điểm sớm nhất để hai máy chủ $a$ và $b$ liên thông tương đương với việc tìm đường đi giữa chúng sao cho thời điểm kích hoạt muộn nhất của các cạnh trên đường đi đạt giá trị nhỏ nhất.

Khi xét các kênh truyền được thêm dần theo thứ tự thời gian, thời điểm đầu tiên hai đỉnh liên thông với nhau chính là bước mà thành phần liên thông chứa đỉnh thứ nhất sáp nhập với thành phần liên thông chứa đỉnh thứ hai.

Xây dựng cây Kruskal Tree bằng cách tạo một nút ảo mang trọng số $i$ nối tới gốc của hai thành phần mỗi khi hợp nhất, sau đó đáp án cho mỗi truy vấn là giá trị tại tổ tiên chung gần nhất của $a$ và $b$ tìm bằng phương pháp Binary Lifting.