LCA - Nút cha chung gần nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

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.

Ví dụ

  • input
    8 1
    1 2
    1 3
    1 4
    1 5
    5 6
    5 7
    5 8
    4
    6 7
    3 4
    5 8
    1 4
    output
    5
    1
    5
    1
Back to Top