Cây tìm kiếm nhị phân: Tổ tiên chung gần nhất trên BST trong O(H)

Mục tiêu kiến thức

• Hiểu tính chất BST: Mọi nút ở cây con trái đều nhỏ hơn gốc, mọi nút ở cây con phải đều lớn hơn gốc.
• Tìm LCA không cần Binary Lifting: Đi từ gốc xuống, nếu cả hai giá trị u, v đều nhỏ hơn nút hiện tại ⇒ sang trái; nếu cả hai đều lớn hơn ⇒ sang phải; nếu phân nhánh ở hai phía hoặc một trong hai bằng nút hiện tại ⇒ nút hiện tại chính là LCA.

Mô tả bài toán

Cho một mảng biểu diễn cây tìm kiếm nhị phân (BST) được xây dựng bằng cách chèn lần lượt N số nguyên phân biệt vào cây ban đầu rỗng. Hãy tìm giá trị của tổ tiên chung gần nhất (LCA) của hai giá trị u và v đã có trong cây.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 2 ≤ N ≤ 10⁵.
• Thời gian: 1000ms. Bộ nhớ: 256MB.