Hiểu bài toán

Cho một cây liên thông có N đỉnh và N-1 cạnh. Bà H xuất phát từ đỉnh 1 và cần tìm một lộ trình đi qua chính xác K đỉnh (bao gồm cả đỉnh xuất phát). Lộ trình ngắn nhất được hiểu là lộ trình có số cạnh đi qua ít nhất. Nếu có nhiều lộ trình ngắn nhất, chỉ cần in ra một lộ trình bất kỳ. Ta cần tìm độ dài lộ trình (số cạnh) và danh sách các đỉnh đi theo thứ tự.

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

Cách Duyệt theo chiều sâu (DFS) để mua sắm

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, k;
vector<int> adj[N];
vector<int> path;

void dfs(int u, int parent, int &rem) {
    if (rem == 0) return;
    path.push_back(u);
    rem--;
    if (rem == 0) return;

    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u, rem);
        if (rem == 0) return;
        path.push_back(u);
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) adj[i].clear();
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }

    path.clear();
    int rem = k; // còn lại bao nhiêu đỉnh cần đi qua
    dfs(1, 0, rem);

    cout << path.size() - 1 << "\n";
    for (int x : path) cout << x << " ";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là giải thuật tối ưu nhất dựa trên quan sát về cấu trúc cây.

Nguyên lý: Lộ trình ngắn nhất để đi qua K đỉnh là một đường đi 'không lặp lại con đường đã đi' trừ khi bắt buộc. Cây là đồ thị không chu trình. Nếu ta duyệt từ gốc (đỉnh 1) theo hướng ưu tiên các nhánh con, ta có thể thu thập các đỉnh một cách hiệu quả.

Thuật toán:

1. Duyệt cây DFS từ đỉnh 1.
2. Tại mỗi nút u, ta thêm u vào lộ trình.
3. Với mỗi con v (không phải cha), ta đi xuống v. Sau khi duyệt xong nhánh v và quay lại u, ta lại thêm u vào lộ trình để làm đường về.
4. Dừng lại khi đã thu thập đủ K đỉnh.

Tại sao hiệu quả?

• Nếu ta có thể lấy đủ K đỉnh chỉ bằng cách đi xuống các nhánh con mà không cần quay lại quá nhiều, độ dài lộ trình sẽ nhỏ.
• Trong cấu trúc cây, cách đi này đảm bảo ta đi qua các đỉnh theo thứ tự ưu tiên (vì input là cây có gốc và thứ tự các con), đảm bảo tìm được lộ trình ngắn nhất.
• Độ dài thực tế của lộ trình (số cạnh) sẽ bằng 2 * (số cạnh trong nhánh được duyệt). Nếu K đủ nhỏ để nằm gọn trong một nhánh, lộ trình rất ngắn. Nếu K lớn, ta phải đi qua nhiều nhánh, lộ trình dài hơn nhưng vẫn tối ưu vì không có đường tắt nào khác.

Ví dụ với Input 1 (N=6, K=2): Ta chỉ cần 2 đỉnh. DFS từ 1, thêm 1. Thêm 2. Đủ K. Lộ trình: 1 2. Độ dài 1.

Cách Tìm đường kính và chọn đoạn

// Ý tưởng này chỉ hiệu quả nếu K nhỏ và nằm trên 1 đường đi đơn giản.
// Tuy nhiên, do yêu cầu phải đi qua chính xác K đỉnh (có thể rẽ nhánh),
// giải thuật DFS (Approach 1) mới là chính xác nhất cho các trường hợp tổng quát.
// Dưới đây là code minh họa cho giải thuật DFS đã tối ưu.

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, k;
vector<int> adj[N];
vector<int> path;
int cnt = 0;

void dfs(int u, int p) {
    if (cnt == k) return;
    path.push_back(u);
    cnt++;
    if (cnt == k) return;

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        if (cnt == k) return;
        path.push_back(u);
    }
}

int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i=1; i<=n; i++) adj[i].clear();
        for (int i=2; i<=n; i++) {
            int p; cin >> p;
            adj[p].push_back(i);
            adj[i].push_back(p);
        }
        path.clear();
        cnt = 0;
        dfs(1, 0);
        cout << path.size() - 1 << endl;
        for (int x : path) cout << x << " ";
        cout << endl;
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Giải thuật này về cơ bản là cách tiếp cận 'Greedy DFS'.

Chi tiết:

• Ta ưu tiên duyệt các node con theo thứ tự từ trái sang phải (được xác định bởi thứ tự input).
• Khi ta đi vào một node con, ta phải đi hết các node trong nhánh đó (hoặc cho đến khi đủ K node) rồi mới quay lại node cha.
• Việc quay lại node cha tính là một bước di chuyển và node cha được ghi nhận lại trong lộ trình.

Phân tích độ dài: Giả sử ta duyệt qua một nhánh con chứa m node (kể cả node con đó).

• Nếu m <= K: Ta đi vào nhánh này, đi hết m node. Ta tốn m-1 bước đi xuống và m-1 bước quay lại (trừ node cuối cùng).
• Nếu m > K: Ta chỉ cần lấy K node đầu tiên trong nhánh này.

Ví dụ: Cây 1-2-3-4-5, K=4. DFS: 1 -> 2 -> 3 -> 4. Đủ 4 node. Lộ trình: 1 2 3 4. (Không cần quay lại).

Ví dụ: Cây 1 có con 2 và 3. 2 có con 4. N=4, K=4. DFS: 1 -> 2 -> 4 -> (quay lại 2) -> (quay lại 1) -> 3. Lộ trình: 1 2 4 2 1 3. Độ dài: 1-2 (1), 2-4 (1), 4-2 (1), 2-1 (1), 1-3 (1) -> 5 cạnh. Số node: 6 (1,2,4,2,1,3).

Nếu ta dùng BFS hay tìm đường kính đơn thuần, ta có thể bỏ lỡ việc rẽ nhánh để lấy node rẻ hơn. DFS đảm bảo ta lấy node theo thứ tự ưu tiên 'gần nhất' trước.

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

Bài học kinh nghiệm

• Vấn đề có thể được giải quyết bằng cách duyệt cây (DFS) để thu thập K đỉnh theo thứ tự ưu tiên. Đây là cách hiệu quả nhất.
• Lộ trình được tạo ra bằng cách ghi nhận node trước khi đi xuống và ghi nhận node cha sau khi quay lại từ con.
• Độ dài lộ trình (số cạnh) bằng số lượng phần tử trong mảng path trừ đi 1.

Lỗi thường gặp

• Lầm tưởng rằng chỉ cần tìm đường đi giữa 2 node xa nhất (đường kính) là đủ. Điều này chỉ đúng nếu K-1 đường đi đó đủ dài. Nếu không, ta cần rẽ nhánh, và DFS là phương pháp đúng.
• Quên rằng node cha được thêm vào lộ trình nhiều lần khi có nhiều nhánh con, dẫn đến sai số độ dài.
• Xử lý sai trường hợp K=1 (chỉ ở đỉnh 1) hoặc K=N (phải đi qua toàn bộ cây).