Đề bài

Cho một cây có gốc và đa nhánh, yêu cầu xác định tổ tiên chung gần nhất (LCA) của hai nút được chỉ định trong mỗi truy vấn.

Dữ liệu nhập

Dòng đầu tiên chứa ba số nguyên dương N, M, S lần lượt là số nút, số truy vấn và nút gốc.

Tiếp theo N-1 dòng, mỗi dòng gồm hai số nguyên x, y biểu thị cạnh nối giữa hai nút.

M dòng tiếp theo, mỗi dòng gồm hai số a, b, cần tìm LCA của a và b.

Dữ liệu xuất

Xuất M dòng, mỗi dòng chứa kết quả cho một truy vấn.

Ví dụ minh họa

Input:

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

Output:

4
4
1
4
4

Phương pháp giải

Thuật toán Tarjan kết hợp duyệt DFS và cấu trúc Union-Find để giải bài toán LCA. Khi duyệt từ gốc, mỗi nút được đánh dấu trạng thái. Sau khi xử lý xong một nhánh con, cập nhật cha của nút trong Union-Find. Với truy vấn liên quan đến nút đang xử lý, nếu nút còn lại đã được duyệt xong, tổ tiên chung gần nhất chính là gốc của nút đó trong Union-Find.

Cài đặt

Dưới đây là mã nguồn C++ triển khai thuật toán:

#include <iostream>
#include <vector>
using namespace std;

const int MAX_SIZE = 500005;

int nodeCount, queryCount, rootNode;
vector<int> treeAdjacency[MAX_SIZE];
vector<pair<int, int>> queryList[MAX_SIZE];
int unionParent[MAX_SIZE];
int visitStatus[MAX_SIZE];
int answers[MAX_SIZE];

int findSet(int x) {
    if (unionParent[x] != x) {
        unionParent[x] = findSet(unionParent[x]);
    }
    return unionParent[x];
}

void processTarjan(int currentNode, int parentNode) {
    visitStatus[currentNode] = 1;
    for (int neighbor : treeAdjacency[currentNode]) {
        if (neighbor == parentNode) continue;
        processTarjan(neighbor, currentNode);
        unionParent[neighbor] = currentNode;
    }
    visitStatus[currentNode] = 2;
    for (auto& q : queryList[currentNode]) {
        int targetNode = q.first;
        int queryIndex = q.second;
        if (visitStatus[targetNode] == 2) {
            answers[queryIndex] = findSet(targetNode);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> nodeCount >> queryCount >> rootNode;
    for (int i = 0; i < nodeCount - 1; i++) {
        int u, v;
        cin >> u >> v;
        treeAdjacency[u].push_back(v);
        treeAdjacency[v].push_back(u);
    }

    for (int i = 1; i <= nodeCount; i++) {
        unionParent[i] = i;
    }

    for (int i = 1; i <= queryCount; i++) {
        int a, b;
        cin >> a >> b;
        queryList[a].emplace_back(b, i);
        queryList[b].emplace_back(a, i);
    }

    processTarjan(rootNode, 0);

    for (int i = 1; i <= queryCount; i++) {
        cout << answers[i] << '\n';
    }

    return 0;
}