Cây N đỉnh được định nghĩa là một đồ thị gồm N nút và N – 1 cạnh, trong đó có một nút làm gốc, các nút có thể có 1 hoặc nhiều nút con, nút không có con gọi là nút lá.
Hai nút u, v có chung một nút cha p nếu như trên đường đi từ gốc tới u, tới v đều qua p. Như vậy hai nút u, v có thể có nhiều nút cha chung.
Vấn đề đặt ra là tìm nút cha chung gần nhất của hai nút u và nút v.
Dữ liệu vào:
- Dòng 1 là hai số N và R (1 <= R <= N <= 105) trong đó N là số nút của cây và G là số hiệu của nút gốc.
- N – 1 dòng tiếp theo, mỗi dòng là một cặp u, v biểu diễn một cạnh
- Dòng thứ N +1 chứa một số K (1 <= K <= 105) là số lượng truy vấn.
- K dòng tiếp theo: mỗi dòng chứa hai số p và q biểu diễn cặp nút cần tìm cha chung gần nhất.
Kết quả ra:
- K dòng, mỗi dòng chứa một số hiệu là nút cha của hai nút p, q tương ứng trong input.