[C++] Build a Tree and Traverse
Solution 1 - Directed Edges\nThe test cases are weak. It says "undirected" in the statement, but somehow this solution can pass all tests.\n\ncpp\nclass Solutio
Solution 1 - Directed Edges\nThe test cases are weak. It says "undirected" in the statement, but somehow this solution can pass all tests.\n\n```cpp\nclass Solution {\npublic:\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n        // Time Complexity: O(n)\n        // Space Complexity: O(n)\n        vector<vector<int>> tree(n);\n        \n        for (const vector<int>& e: edges)\n            tree[e[0]].push_back(e[1]);\n        \n        function<pair<bool, int>(int)> dfs = [&](int curr) {\n\t\t\t// bool: if any node in the sub-tree has an apple\n\t\t\t// int: distance we accumulate so far\n            pair<bool, int> ans = {hasApple[curr], 0};\n            \n            for (const int& child: tree[curr]) {\n                pair<bool, int> p = dfs(child);\n                if (p.first) {\n\t\t\t\t\t// if we find any apple below, we reach the child and come back\n\t\t\t\t\t// update the state whether we have found any apple\n                    ans.second += p.second + 2;\n                    ans.first = true;\n                }\n            }\n            return ans;\n        };\n        \n        return dfs(0).second;\n    }\n};\n```\n\n```cpp\nclass Solution {\npublic:\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n        // Time Complexity: O(n)\n        // Space Complexity: O(n)\n        vector<int> dist(n);\n        \n        for (int i = (int) edges.size() - 1; i >= 0; --i)\n            if (hasApple[edges[i][1]]) {\n                hasApple[edges[i][0]] = true;\n                dist[edges[i][0]] += dist[edges[i][1]] + 2;\n            }\n        \n        return dist[0];\n    }\n};\n```\n\nSolution 2 - Undirected Edges\n\n```cpp\nclass Solution {\npublic:\n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n        // Time Complexity: O(n)\n        // Space Complexity: O(n)\n        vector<vector<int>> tree(n);\n        \n        for (const vector<int>& e: edges) {\n            tree[e[0]].push_back(e[1]);\n            tree[e[1]].push_back(e[0]);\n        }\n        \n        function<int(int, int)> dfs = [&](int curr, int parent) {\n            int ans(0);\n            \n            for (const int& child: tree[curr]) {\n                if (child == parent) continue;\n                int prev = dfs(child, curr);\n                if (prev > 0 || hasApple[child]) ans += prev + 2;\n            }\n            \n            return ans;\n        };\n        \n        return dfs(0, -1);\n    }\n};\n```
[]