#865. LCA - Cha chung gần nhất

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho một cây có N đỉnh, các đỉnh được đánh số từ 1 đến N , gốc tại đỉnh 1 . Hãy trả lời Q truy vấn tìm LCA của hai đỉnh u v .

Dữ liệu vào:

  • Dòng đầu tiên là số N ;
  • N-1 dòng tiếp theo thể hiện cạnh của cây;
  • Dòng tiếp theo là số Q ;
  • Q dòng tiếp theo là cặp (u,v) 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:

3
7
1
1
6
1

Giới hạn:

  • 1\le N, Q \le 10^5 .