Hiểu bài toán

Cho một cây có n đỉnh với gốc là nút 1. Có q truy vấn. Mỗi truy vấn cho một tập hợp k nút khác nhau. Nhiệm vụ là tìm hai nút trong tập hợp đó sao cho tổ tiên chung gần nhất (LCA) của chúng nằm ở độ sâu nhỏ nhất (gần gốc nhất). In ra LCA đó. Giả sử Depth(root) = 0.

Các cách tiếp cận

Cách Brute Force (Tất cả cặp)

int best_depth = -1;
int best_node = -1;
for (int i = 0; i < k; i++) {
    for (int j = i + 1; j < k; j++) {
        int u = nodes[i];
        int v = nodes[j];
        int l = lca(u, v);
        if (best_depth == -1 || depth[l] < best_depth) {
            best_depth = depth[l];
            best_node = l;
        }
    }
}
// O(k^2 * logN) per query

• Time Complexity: O(k^2 * logN)
• Space Complexity: O(1)

Cách này đơn giản nhất: thử tất cả các cặp (u, v) trong k nút cho trước, tính LCA của từng cặp và chọn ra LCA có độ sâu nhỏ nhất. Tuy nhiên, độ phức tạp quá cao, không thể chạy đúng với k lớn (ví dụ k=10^5).

Cách Tối ưu hóa bằng cách chọn nút đại diện

// Giả sử đã có mảng depth[] và hàm lca(u, v)
int query(const vector<int>& nodes) {
    int u = nodes[0];
    for (int i = 1; i < nodes.size(); i++) {
        u = lca(u, nodes[i]);
    }
    return u;
}
// O(k * logN)

• Time Complexity: O(k * logN)
• Space Complexity: O(1)

Giả sử ta có một nút 'tổ tiên chung' tạm thời U. Khi xét thêm một nút V mới, ta thay thế U bằng LCA(U, V). Sau khi xét hết k nút, U sẽ là LCA của tất cả k nút đó. Tuy nhiên, đáp án bài toán KHÔNG phải là LCA của tất cả k nút. Ví dụ: Cây 1-2-3-4. Nodes {2, 4}. LCA(2, 4) = 2. LCA của tất cả nodes là 2. Nodes {2, 3, 4}. LCA(2, 4) = 2. LCA(2, 3) = 2. LCA(3, 4) = 3. LCA của tất cả nodes {2, 3, 4} là 2 (vì 2 là cha của 3, 4). Nhưng LCA của cặp (3, 4) là 3, nằm sâu hơn 2. Vậy cách này chỉ đúng nếu ta tìm LCA của TẤT CẢ các nút, nhưng bài toán yêu cầu tìm LCA của một CẶP nút sao cho LCA đó nằm sâu nhất (gần gốc nhất). Trong ví dụ trên, LCA=2 (nằm ở độ sâu 1) tốt hơn LCA=3 (nằm ở độ sâu 2). Vậy cách này đúng: LCA của cặp (u, v) càng gần gốc (độ sâu nhỏ) thì越好. LCA của cả tập hợp chính là LCA của mọi cặp có thể có (vì LCA(a,b,c) = LCA(LCA(a,b), c)). Nếu LCA cả tập hợp nằm ở độ sâu D, thì mọi cặp LCA đều có độ sâu >= D. Do đó, LCA cả tập hợp chính là đáp án tối ưu. *Lưu ý: Câu hỏi bài toán là 'LCA gần gốc nhất' -> Depth nhỏ nhất. LCA của cả tập hợp chính là node nằm nông nhất. Vậy cách này là đúng và tối ưu.

Cách Giải thuật tối ưu (Dùng 2 nút cực đoan)

// Tìm node có depth nhỏ nhất (gần gốc nhất) trong tập hợp
int min_depth_node = nodes[0];
for (int x : nodes) {
    if (depth[x] < depth[min_depth_node]) min_depth_node = x;
}

// Tìm node cách min_depth_node xa nhất (dựa trên khoảng cách LCA)
// Hoặc đơn giản hơn: LCA của tập hợp là node có depth nhỏ nhất trong tập hợp?
// KHÔNG. Ví dụ: Cây 1-2-3, 1-4. Nodes {2, 4}. Depth=1 cả 2. LCA(2,4)=1 (Depth=0).
// Vậy node có depth nhỏ nhất trong tập hợp KHÔNG phải là LCA.

// Đúng là: LCA của tập hợp các node {v1, v2, ..., vk} là node có depth nhỏ nhất mà là tổ tiên của tất cả các node đó.
// Ta có thể dùng cách sau:
// 1. Lấy node u có depth nhỏ nhất trong tập hợp.
// 2. Lấy node v có depth nhỏ nhất trong tập hợp SAU KHI loại bỏ các node cháu của u (nếu có).
//    (Nếu v là con cháu của u, thì LCA(u, v) = u. Nếu v không phải con cháu, LCA(u, v) có depth < depth(u)).

// Tuy nhiên, cách đơn giản nhất và an toàn nhất trong giới hạn tổng k là 200,000 là:
// Sắp xếp các node theo mốc thời gian DFS (tin).
// LCA của tập hợp là LCA của node có tin nhỏ nhất và node có tin lớn nhất.

void solve_approach_3() {
    // Sắp xếp nodes theo tin
    sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
    int u = nodes.front();
    int v = nodes.back();
    // LCA(u, v) chính là LCA của cả tập hợp.
    int ans = lca(u, v);
}
// Độ phức tạp: O(k log k) do sort.
// Có thể tối ưu thành O(k) nếu dùng Min/Max theo tin mà không sort full.

• Time Complexity: O(k log k)
• Space Complexity: O(k)

Một đặc điểm quan trọng của LCA và mốc thời gian DFS (tin): Node A là tổ tiên của node B nếu và chỉ nếu tin[A] <= tin[B] && tout[A] >= tout[B]. Đối với một tập hợp các node, LCA của chúng chính là LCA của node có mốc thời gian DFS nhỏ nhất và node có mốc thời gian DFS lớn nhất. Giải thuật:

1. Tìm node u có giá trị tin nhỏ nhất trong tập hợp.
2. Tìm node v có giá trị tin lớn nhất trong tập hợp.
3. Kết quả là LCA(u, v). Điều này đúng vì:

• Nếu tất cả các node nằm trên cùng một nhánh (ví dụ: 1-2-3-4), node có tin nhỏ nhất là node cao nhất (gần root nhất), node có tin lớn nhất là node thấp nhất. LCA của chúng là node cao nhất. Đây là LCA của cả tập hợp.
• Nếu các node nằm trên các nhánh khác nhau (ví dụ: node 2 và node 4 trong hình 1-2, 1-4), node có tin nhỏ nhất nằm ở nhánh này, node có tin lớn nhất nằm ở nhánh kia. LCA của chúng là node chung (root). Đây là LCA của cả tập hợp.

Độ phức tạp: Nếu sort: O(k log k). Nếu duyệt tìm min/max theo tin: O(k). Tổng k qua các query là 2*10^5, nên O(k log k) hoàn toàn chấp nhận được.

Phân tích độ phức tạp

Bài học kinh nghiệm

• LCA của một tập hợp các node chính là LCA của node có mốc thời gian DFS (tin) nhỏ nhất và node có mốc thời gian DFS lớn nhất trong tập hợp đó.
• Bài toán yêu cầu tìm cặp (u, v) sao cho LCA(u, v) gần gốc nhất. Điều này tương đương với việc tìm LCA của cả tập hợp (vì LCA của cả tập hợp là node chung nằm cao nhất).

Lỗi thường gặp

• Lầm tưởng rằng node có độ sâu nhỏ nhất trong tập hợp chính là đáp án. (Ví dụ root là node có depth nhỏ nhất nhưng root có thể không phải là LCA của bất kỳ cặp nào nếu所有节点都在root下面 sâu hơn, nhưng root là LCA của cặp ở 2 nhánh khác nhau).
• Quên rằng tổng k qua các query là 200,000, nên thuật toán O(k log k) là hoàn toàn khả thi.