Thời gian tối thiểu thu thập tất cả táo trong cây (Minimum Time to Collect All Apples in a Tree) trong C++

Cho cây không hướng n đỉnh (0 đến n-1), một số đỉnh có táo. Di chuyển qua một cạnh tốn 1 giây. Bắt đầu từ đỉnh 0, thu thập tất cả táo và quay lại 0. Tìm thời gian tối thiểu.

Ví dụ

Đầu vào: n=7, edges=[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple=[f,f,t,f,t,t,f]
Đầu ra: 8.

Thuật toán DFS pós-order

Quan sát: một cạnh cần đi qua (2 lần: đi và về) nếu và chỉ nếu cây con phía dưới cạnh đó chứa ít nhất một táo.

1. Xây dựng danh sách kề.
2. DFS từ 0, tham số parent tránh quay lại.
3. Hàm DFS trả về true nếu cây con gốc tại node hiện tại có táo (bao gồm chính node).
4. Nếu con trả về true → cộng 2 vào kết quả (đi và về cạnh đó).
5. Trả về hasApple[node] || any_child_has_apple.

Triển khai C++

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

class Solution {
    int ans = 0;
    bool dfs(int u, int p, const vector<bool>& apple, const vector<vector<int>>& g) {
        bool has = apple[u];
        for (int v : g[u]) if (v != p) {
            if (dfs(v, u, apple, g)) {
                ans += 2;
                has = true;
            }
        }
        return has;
    }
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        dfs(0, -1, hasApple, g);
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt cây một lần.
• Không gian: O(N) - đồ thị và ngăn xếp đệ quy.

Kết quả kiểm thử

Đầu vào: 7, {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}}, {f,f,t,f,t,t,f}
Đầu ra: 8