#866. LCA2 - Cha chung gần nhất (gốc thay đổi)

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: Trùm CUỐI

Đề bài

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

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à bộ ba số (u, v, r) cần tìm LCA của u v với gốc là đỉnh r .

Dữ liệu ra:

  • In ra Q dòng tương tứng đáp án cho Q câu hỏi.

Ví dụ:

Dữ liệu vào:

5
5 3
5 4
2 5
3 1
5
3 1 1
5 2 3
2 2 1
1 5 5
3 3 5

Dữ liệu ra:

1
5
2
5
3

Giới hạn:

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