Cho một cây có đỉnh, các đỉnh được đánh số từ đến , gốc tại đỉnh . Hãy trả lời truy vấn tìm LCA của hai đỉnh và .
Dữ liệu vào:
- Dòng đầu tiên là số ;
- dòng tiếp theo thể hiện cạnh của cây;
- Dòng tiếp theo là số ;
- dòng tiếp theo là cặp cần tìm LCA của chúng.
Dữ liệu ra:
- Với mỗi truy vấn, in ra LCA của hai đỉnh đã cho.
Ví dụ:
Dữ liệu vào:
7
6 1
6 4
4 7
3 4
1 2
2 5
6
3 3
7 7
1 3
5 7
7 6
2 4
Dữ liệu ra:
Giới hạn:
